pku_1699_Best Sequence
【题目概述】求N（N<=10）个子串的最短和串，且不会发生一个完全包涵另外一个的现象。
【题目分析】简单的状态DP问题，一开始想用字符串的思想解决，发现状态之间，不好变换。正好自己做压缩DP的专题，还是，用这个方法吧！
1. 对于每个字符串的放置，和她有直接影响的是上一个字符的放置情况。由此，我们可以建立一个状态转移方程
设 表示当前状态s以第i个字符串结尾产生的最小和串的长度。则
2. 若s只包含一个串的时候， 其中len[i]表示第i个子串的长度。
3. 否则，如果当前的状态合法，且s状态集中，不包含有j串，那么,， 记
a) 如果 其中，com[I, j] 表示第i个串之后是第j个串的公共子串的长度。
b) 否则，不处理。
4. 最后的结果就是， i是所有的子串。
【题目代码】：
//Name: pku_1699_Best Sequence
#include <iostream>
#include <cstring>
using namespace std;
const int inf = 1<<20;
const int maxn = 1<<10;
char str[10][20];
int len[10], com[20][20], n, m;
int dp[maxn][10], ans;
void Link(int x, int y) {
int i, j, k, mlen = min(len[x], len[y]);
for (k = mlen; k >= 0; k--) {
for (i = len[x]-k, j = 0; i < len[x]; i++, j++)
if (str[x][i] != str[y][j]) break;
if (i == len[x]) {
com[x][y] = k; break;
}
}
for (k = mlen; k >= 0; k--) {
for (i = len[y]-k, j = 0; i < len[y]; i++, j++)
if (str[y][i] != str[x][j]) break;
if (i == len[y]) {
com[y][x] = k; break;
}
}
}
int main() {
// freopen("in.in", "r", stdin);
int t, i, j, s, r; scanf("%d", &t);
while(t-- && scanf("%d", &n)) {
memset(com, 0, sizeof(com));
for(i = 0; i < n; i++) {
scanf("%s", str+i);
len[i] = strlen(str[i]);
for (j = 0; j < i; j++) Link(i, j);
}
// for(i = 1; i < n; i++) printf("%d\n", com[i-1][i]);
for(i = 1; i < 1<<n; i++)
for (j = 0; j < n; j++) dp[i][j] = inf;
for(i = 0; i < n; i++) dp[1<<i][i] = len[i];
for(s = 1; s < 1<<n; s++) {
for (i = 0; i < n; i++) if(s&(1<<i)) {
for(j = 0; j < n; j++) if(i!=j && !(s&(1<<j))) {
r = s|(1<<j);
dp[r][j] = min(dp[r][j], dp[s][i] - com[i][j] + len[j]);
// printf("dp[%d][%d] = %d\n", r, j, dp[r][j]);
}
}
}
// for(i = 0; i < n; i++) printf("%d\n", dp[s-1][i]);
ans = inf;
for(i = 0; i < n; i++)
if (dp[s-1][i] < ans) ans = dp[s-1][i];
printf("%d\n", ans);
}
return 0;
}