



BlockEnemy
Since tree is given in the problem statement, we should try DP on subtrees first=) Given any correct solution for the whole tree, any subtree of it is also correct. So if all pairs of occupied towns are separated, then in each subtree they are also separated. So we can try to use state domain (v)>R where v represents subtree and R represents minimal effort to solve the problem for this subtree. But we'll discover soon that connecting subtrees correctly is impossible because we need to know whether there is an occupied town connected with outside part of subtree. We call such a solution for subtree dangerous. Now we add the boolean parameter (solution is safe/dangerous) in the state domain. Let res[v][t] be the minimal effort needed to get a correct solution for vsubtree which is dangerous(if d=1)/safe(if d=0). Initially we consider edge which is going out of subtree indestructible. We will handle the destruction of outgoing edge later. In this case, the solution for leaves is easy to obtain. If v is nonoccupied leaf, then it forms a safe solution, and dangerous solution is impossible to get. If it is occupied, then the solution is dangerous with no effort, and impossible to make safe. Then if the vertex v is not leaf, we add its sons one by one. When adding a son s to vsubtree, we have the following merging rules: 1. v=safe + s=safe > v=safe 2. v=dangerous + s=safe > v=dangerous 3. v=safe + s=dangerous > v=dangerous 4. v=dangerous + s=dangerous > incorrect solution After merging by these rules, we receive a solution for vsubtree in case of indestructible outgoing edge. Now what changes if the outgoing edge is destructible? We can destruct it by paying additional effort. In this case a dangerous solution turns into safe one. The root of tree has no outgoing edge. The problem answer is minimal effort of safe and dangerous solutions for the root ot DFS tree. The time complexity is O(N^2) because adjacency matrix is used, but can be easily reduced to O(N) with neighbors lists.
int res[MAXN][2];
void DFS(int v, int f) { //traverse vsubtree, f is father of v
vis[v] = true; //mark v as visited
res[v][0] = (occ[v] ? 1000000000 : 0); //result in case of leaf
res[v][1] = (occ[v] ? 0 : 1000000000);
for (int s = 0; s<n; s++) if (matr[v][s] < 1000000000) {
if (vis[s]) continue; //iterate over all sons
DFS(s, v); //run DFS recursively
int nres[2];
nres[0] = res[v][0] + res[s][0]; //safe case requires safe s and safe v
nres[1] = min(res[v][0] + res[s][1], res[v][1] + res[s][0]);
res[v][0] = nres[0]; //dangerous case requires dangerous + safe
res[v][1] = nres[1];
}
if (f >= 0 && res[v][0] > res[v][1] + matr[v][f]) //we can destroy upgoing edge (vf)
res[v][0] = res[v][1] + matr[v][f];
}
...
DFS(0, 1); //run DFS from 0 (with no father)
return min(res[0][0], res[0][1]); //whether root is dangerous does not matter
}


ConstructionFromMatches
We need to construct grid from matches obeying certain rules which have local effect. And the grid is 2 x n which is ideal for DP with profiles. Of course, it is better to slice the grid to 2cell layers instead of Ncell ones. The profile consists of thicknesses of the last two vertical sticks. They are required to check sum when filling the next layer. To perform the transition, we have to iterate through all possible variants of next five sticks thicknesses and choose only variants that satisfy two equations on cell sums. If we perform it bruteforce, we will get O(N*K^7) algorithm, that's slow. It can be easily optimized if we calculate thicknesses of two sticks explicitly by using cell sum equations. This way the DP will be O(N*K^5) in time and O(N*K^2) in space. That is more than enough for the problem. If you want a better solution, you can notice that: 1. You can use "storing two layers" optimization and reduce space complexity to O(K^2). 2. You can transform the solution to DP with broken profiles. To do it you should add intermediate "half" states (i,p,b,v). hres[i][p][b][v] means minimal cost of full construction of (2*i+1) cells  i layers and a top cell in the next layer. The DP with broken profiles will require O(N*K^4) time and O(N*K^3) space, which can be reduced with technique 1 to O(K^3). The code for simple solution is given below. Since width of profile is wellknown and very small, it is easier to write transition code as nested loops instead of recursive search.
//...?? aa //schema of profile and transition
//... u p //u and v comprise profile
//... u p //a, b, c, p, q are five added sticks
//...?? bb //system of equations is:
//... v q //{u + a + p + b = top[i]
//... v q //{v + b + q + c = bottom[i]
//...?? cc //the depicted transition leads to (i+1,p,q) state
memset(res, 63, sizeof(res)); //DP base
for (int u = 0; u<k; u++) //choose any two sticks
for (int v = 0; v<k; v++) //put them to leftmost vertical line
res[0][u][v] = cost[u] + cost[v]; //their cost is clear
for (int i = 0; i<n; i++)
for (int u = 0; u<k; u++)
for (int v = 0; v<k; v++) { //iterate through states
int cres = res[i][u][v];
for (int a = 0; a<k; a++) //choose a and p in all possible ways
for (int p = 0; p<k; p++) {
int b = top[i]4  (u + a + p); //b is uniquely determined by top equation
if (b < 0  b >= k) continue; //though it can be bad...
for (int q = 0; q<k; q++) { //choose all possible q variants
int c = bottom[i]4  (v + b + q); //c is uniquely determined by bottom equation
if (c < 0  c >= k) continue;
int nres = cres + cost[p] + cost[q] //the new solution cost
+ cost[a] + cost[b] + cost[c];
if (res[i+1][p][q] > nres) //relaxing the destination
res[i+1][p][q] = nres;
}
}
}
int answer = 1000000000; //the last two sticks do not matter
for (int u = 0; u<k; u++) //choose the best variant among them
for (int v = 0; v<k; v++)
if (answer > res[n][u][v])
answer = res[n][u][v];
if (answer >= 1000000000) answer = 1; //do not forget "impossible" case


This recipe is great, in my opinion, considering there's a few interesting tutorials about dp in the web (not just knapsack and LCS but with some more content) if any. Sought for one some time ago (especially wanted to read about dp over subsets) and now I have a chance to read it. I mean it's good not only for Cookbook but for me so thank you very much. 

Thank you! This is the most useful recipe I have read so far. Perhaps it will finally help me to understand DP and move to yellow... 

For the multidimensional array, I don't understand what does Result[i1][i2][i3]...[ik] represent in terms of the Knapsack problem? Does it mean the maximum cost that we can obtain by using i1 number of items 1, i2 number of items2, ..., ik number of kth item? If so, then it is no longer 01 Knapsack, but more like unbounded Knapsack. By the way, it will be great if you can use the Knapsack example for all the representation types. 

For the subsets of a given set you should mention that M[x,y] is the distance between cities x and y. You should use M in the code (instead of matr). You should explain the reasoning behind R[X,a]+M[a,0]: R[x,a] is the shortest path that visits every node once starting from node 0, so R[X,a]+M[a,0] is the shortest Hamilton cycle for X. 

For substrings of a given string. Can you avoid using 'l' in the code, because it looks too similar to one. You can use L and R instead. What is "tres=?;"? What is a in this case and is it actually used in the code? 

1. The Result[i1,i2,...,ik] has nothing is common with knapsack. It is array of results for general problem with multidimlike state domain. Knapsack was an example of such a problem with dim=2.
2. I added explanation for M matrix and about the way answer is got. About M and matr  it is usual thing. Mathematics is used to short variable names (12 letters) whereas in programming short names is bad habbit. I have a strong feeling against naming a matrix with one letter, sorry=) By the way, didn't you notice that state result is denoted as R in text but as res in code?...
3. Changed l,m,r to L,M,R. (l+1) looks really weird=) Question mark represents something that depends on the problem. It is usually neutral element i.e. 0 in combinatoric problem, +inf in minimization problem, inf in maximization problem. I don't want to explain it here and there may be exceptions. That's why I just put question mark. Look one of examples and you'll see 10^18 in this place.
a represents additional parameters. It must be explained somewhere in the recipe=) I added a note on this to the first place it is met.
I don't like that additional parameters are represented by letter "a". Because it is english article also... I've enclosed parameter "a" in quotes in most places in text so that the do not confuse reader. 

This is a great post! Thanks for sharing it and congrats you are a smart guy! 
