求用一个串的四个子串能覆盖原串的最大和最小长度。
比赛的时候没有出这一题，其实思路上差不多都是对的，但细节上没有实现好。。
三维的字符串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 }