Examples:
InformFriends
We are asked to find assignment man>fact which maximizes the number of facts with constraint that everyone must know all the facts. In the optimal assignment people can be divided into factgroups. Each factgroup consists of people who are told the same fact. And each factgroup must be able to tell everybody else about the fact. Let's precalculate for each subset of people whether they can become a factgroup. The subset can be a factgroup if set of all thier friends united with them is the whole set. After possible factgroups are calculated, we have to determine maximal number of nonintersecting factgroups in the set of people. We can define state domain (s)>R where s is subset of people and R is problem answer for them. To determine the answer for state s we have to subtract one of its factgroups. It is a subset of s and forms a factgroup. So we can iterate through all subsets of s and try them as factgroups.
n = matr.size();
int i, j, u;
for (i = 0; i<(1<<n); i++) { //for all subsets i
int mask = 0;
for (j = 0; j<n; j++) if (i&(1<<j)) { //iterate through people in it
mask = (1<<j);
for (u = 0; u<n; u++) if (matr[j][u]=='Y') //accumulate the total set of informed people
mask = (1<<u);
}
cover[i] = (mask == (1<<n)1); //if everyone is informed, the subset if factgroup
}
int ans = 0;
for (i = 0; i<(1<<n); i++) { //go through states
res[i] = 0;
for (j = i; j>0; j = (j1)&i) if (cover[j]) //iterate through all factgroup subsets
if (res[i] < res[i^j] + 1)
res[i] = res[i^j] + 1; //relax the result for i
if (ans < res[i]) ans = res[i]; //relax the global answer
}
return ans;
Breaking strings (ZOJ 2860)
This problem is solved with DP over substrings. Let's enumerate all required breaks and two ends of string with numbers 0, 1, 2, ..., k. Then res[L,R] will be result for the substring which starts in Lth point and ends in Rth point. To get this result we should look through all possible middle points M and consider res[L][M] + res[M][R] + (x[R]x[L]) as a result. By doing this we get a clear O(k^3) solution (which is TL). What makes this problem exceptional is the application of Knuth's optimization. This trick works only for optimization DP over substrings for which optimal middle point depends monotonously on the end points. Let mid[L,R] be the first middle point for (L,R) substring which gives optimal result. It can be proven that mid[L,R1] <= mid[L,R] <= mid[L+1,R]  this means monotonicity of mid by L and R. If you are interested in a proof, read about optimal binary search trees in Knuth's "The Art of Computer Programming" volume 3 binary search tree section. Applying this optimization reduces time complexity from O(k^3) to O(k^2) because with fixed s (substring length) we have m_right(L) = mid[L+1][R] = m_left(L+1). That's why nested L and M loops require not more than 2k iterations overall.
for (int s = 0; s<=k; s++) //s  length(size) of substring
for (int L = 0; L+s<=k; L++) { //L  left point
int R = L + s; //R  right point
if (s < 2) {
res[L][R] = 0; //DP base  nothing to break
mid[L][R] = l; //mid is equal to left border
continue;
}
int mleft = mid[L][R1]; //Knuth's trick: getting bounds on M
int mright = mid[L+1][R];
res[L][R] = 1000000000000000000LL;
for (int M = mleft; M<=mright; M++) { //iterating for M in the bounds only
int64 tres = res[L][M] + res[M][R] + (x[R]x[L]);
if (res[L][R] > tres) { //relax current solution
res[L][R] = tres;
mid[L][R] = M;
}
}
}
int64 answer = res[0][k];
