求用一个串的四个子串能覆盖原串的最大和最小长度。
比赛的时候没有出这一题，其实思路上差不多都是对的，但细节上没有实现好。。
三维的字符串DP，首先处理出每个子串能够开始的位置，这个暴力一下就行。然后用d[i][j][k]表示长度为i状态为j从当前位置开始已经有k个字符被覆盖的最小长度，j是个四位的二进制状态，为1代表已经使用了这个串。当前位置可以选择使用或者不使用新的未使用子串，DP的时候采用刷表会好写的多。
最小和最大的求法是一样的，开两个数组会爆空间。。改用short就行了。。其实写个函数也挺方便的。。
1 #include <string.h> 2 #include <stdio.h> 3 #include <algorithm> 4 #define MAXN 5000 5 #define MAXM 70 6 using namespace std; 7 char s[MAXN], ss[MAXM]; 8 short lens[4], len, maxl; 9 short flag[MAXN], d1[MAXN][16][65], d2[MAXN][16][65]; 10 int main() { 11 while (scanf("%s", s) != EOF) { 12 len = strlen(s); 13 memset(flag, 0, sizeof(flag[0])*len); 14 for (int i = 0; i < 4; i++) { 15 scanf("%s", ss); 16 lens[i] = strlen(ss); 17 for (int j = 0, k; j+lens[i] <= len; j++) { 18 for (k = 0; ss[k]; k++) if (s[j+k] != ss[k]) break; 19 if(ss[k] == '\0') flag[j] |= 1<<i; 20 } 21 if (lens[i] > maxl) maxl = lens[i]; 22 } 23 memset(d1, 0x3f, sizeof(d1[0])*(len+1)); 24 memset(d2, 0xc3, sizeof(d1[0])*(len+1)); 25 d1[0][0][0]=d2[0][0][0]=0; 26 for (int i = 0; i < len; i++) { 27 for (int j = 0; j < 16 ;j++) { 28 for (int k = 0; k <= maxl; k++) { 29 d1[i+1][j][k?k-1:0] = min(d1[i][j][k], d1[i+1][j][k?k-1:0]); 30 d2[i+1][j][k?k-1:0] = max(d2[i][j][k], d2[i+1][j][k?k-1:0]); 31 for (int x = 0; x < 4; x++) { 32 if ((1<<x&~j) && (1<<x&flag[i])) { 33 short t = max((short)k, lens[x]); 34 d1[i][1<<x|j][t] = min((short)(d1[i][j][k]+t-k), d1[i][1<<x|j][t]); 35 d2[i][1<<x|j][t] = max((short)(d2[i][j][k]+t-k), d2[i][1<<x|j][t]); 36 } 37 } 38 } 39 } 40 } 41 printf("%hd %hd\n", d1[len][15][0], d2[len][15][0]); 42 } 43 return 0; 44 }