http://poj.org/problem?id=2817
这个题的意思是第一行给出case数N (1 <= N <= 10)，然后给出N个单词，每个一行，当输入不是正整数的时候结束。每个单词最多10个字母。
Sample Input
5
abc
bcd
cde
aaa
bfcde
0
要求的是，按任意顺序排列这些单词，可以在单词前面加任意个空格，使得相邻的单词上下对应的字母数目最多，并输出最多是多少。
Sample Output
8
比如sample里面的8，是这样得来的：
aaa
abc
bcd
cde
bfcde
注意只有相邻单词的字母上下对应才算对应。
Sample Input
5
abc
bcd
cde
aaa
bfcde
0
要求的是，按任意顺序排列这些单词，可以在单词前面加任意个空格，使得相邻的单词上下对应的字母数目最多，并输出最多是多少。
Sample Output
8
比如sample里面的8，是这样得来的：
aaa
abc
bcd
cde
bfcde
注意只有相邻单词的字母上下对应才算对应。
/*
由于每两个串的最大相同 字符数 是一定的，所以 这个我们是要考虑一个排列使 ，公共字符最多
状态压缩 ， dp[i][j] 表示 在 状态 i 时 以 串 j 结尾的 最大 个数
dp[i][j] = max(dp[k][x]) (x 是没有 被选的 ，k == i &(~(1<<x)))
*/
由于每两个串的最大相同 字符数 是一定的，所以 这个我们是要考虑一个排列使 ，公共字符最多
状态压缩 ， dp[i][j] 表示 在 状态 i 时 以 串 j 结尾的 最大 个数
dp[i][j] = max(dp[k][x]) (x 是没有 被选的 ，k == i &(~(1<<x)))
*/
1 #include<cstdio>
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define Min(a,b) a<b?a:b
12 #define Max(a,b) a>b?a:b
13 #define CL(a,num) memset(a,num,sizeof(a));
14 #define maxn 520
15 #define eps 1e-8
16 #define inf 100000000
17
18 #define ll __int64
19 using namespace std;
20 int len[12];
21 char word[12][12] ;
22 int dp[1500][12] ;
23 int n;
24 int com[12][12] ;
25 int cal(int a,int b)//计算最大 公共字符数
26 {
27 int i,j;
28 int mx = 0;
29 int sum ;
30 for(i = 0 ; i < len[a];i++)
31 {
32 sum = 0;
33 for(j = 0;j + i < len[a] && j < len[b] ;j++)
34 {
35
36 if(word[a][i + j] == word[b][j]) sum ++;
37
38
39 }
40 if(sum > mx) mx = sum ;
41 }
42 for(i = 0;i< len[b];i++)
43 {
44 sum = 0;
45 for(j = 0 ; j + i< len[b] && j< len[a];j++)
46 {
47 if(word[b][i + j] == word[a][j])sum ++;
48
49 }
50 if(sum > mx) mx = sum ;
51 }
52 return mx ;
53 }
54 int get(int stat ,int k)
55 {
56 int i;
57 if(stat == 0) return 0;
58 if(dp[stat][k]) return dp[stat][k];
59
60 stat &= (~(1<<k)) ;
61 int mx = 0 ,d;
62 for(i = 0 ;i < n;i++)
63 { int tmp = stat&(~(1<<i)) ;
64 if(tmp != stat)
65 {
66 d = get( tmp ,i) + com[i][k] ;
67 if(d > mx) mx = d;
68 }
69
70
71 }
72 dp[stat][k] = mx ;
73
74 return dp[stat][k] ;
75 }
76 int main()
77 {
78 int i,j;
79 while(scanf("%d",&n),n>0)
80 {
81 CL(dp,0);
82 for(i = 0; i < n;i++)
83 {
84 scanf("%s",word[i]);
85 len[i] = strlen(word[i]);
86 }
87 for(i = 0; i <n ;i++)
88 {
89 for(j = i+1;j<n;j++)
90 {
91 com[i][j] = com[j][i] = cal(i,j);
92
93 }
94
95 }
96
97 /*for(i = 0; i < n;i++)
98 {
99 for(j = 0 ; j< n;j++)
100 printf("%d ",com[i][j]);
101
102 printf("\n");
103 }*/
104
105 int stat = (1<<n) - 1;
106
107 int ans = 0,tmp;
108 for(i = 0 ; i < n;i++)
109 {
110 tmp = get(stat,i);
111 if(tmp > ans)ans = tmp ;
112 }
113 printf("%d\n",ans);
114 }
115 }
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define Min(a,b) a<b?a:b
12 #define Max(a,b) a>b?a:b
13 #define CL(a,num) memset(a,num,sizeof(a));
14 #define maxn 520
15 #define eps 1e-8
16 #define inf 100000000
17
18 #define ll __int64
19 using namespace std;
20 int len[12];
21 char word[12][12] ;
22 int dp[1500][12] ;
23 int n;
24 int com[12][12] ;
25 int cal(int a,int b)//计算最大 公共字符数
26 {
27 int i,j;
28 int mx = 0;
29 int sum ;
30 for(i = 0 ; i < len[a];i++)
31 {
32 sum = 0;
33 for(j = 0;j + i < len[a] && j < len[b] ;j++)
34 {
35
36 if(word[a][i + j] == word[b][j]) sum ++;
37
38
39 }
40 if(sum > mx) mx = sum ;
41 }
42 for(i = 0;i< len[b];i++)
43 {
44 sum = 0;
45 for(j = 0 ; j + i< len[b] && j< len[a];j++)
46 {
47 if(word[b][i + j] == word[a][j])sum ++;
48
49 }
50 if(sum > mx) mx = sum ;
51 }
52 return mx ;
53 }
54 int get(int stat ,int k)
55 {
56 int i;
57 if(stat == 0) return 0;
58 if(dp[stat][k]) return dp[stat][k];
59
60 stat &= (~(1<<k)) ;
61 int mx = 0 ,d;
62 for(i = 0 ;i < n;i++)
63 { int tmp = stat&(~(1<<i)) ;
64 if(tmp != stat)
65 {
66 d = get( tmp ,i) + com[i][k] ;
67 if(d > mx) mx = d;
68 }
69
70
71 }
72 dp[stat][k] = mx ;
73
74 return dp[stat][k] ;
75 }
76 int main()
77 {
78 int i,j;
79 while(scanf("%d",&n),n>0)
80 {
81 CL(dp,0);
82 for(i = 0; i < n;i++)
83 {
84 scanf("%s",word[i]);
85 len[i] = strlen(word[i]);
86 }
87 for(i = 0; i <n ;i++)
88 {
89 for(j = i+1;j<n;j++)
90 {
91 com[i][j] = com[j][i] = cal(i,j);
92
93 }
94
95 }
96
97 /*for(i = 0; i < n;i++)
98 {
99 for(j = 0 ; j< n;j++)
100 printf("%d ",com[i][j]);
101
102 printf("\n");
103 }*/
104
105 int stat = (1<<n) - 1;
106
107 int ans = 0,tmp;
108 for(i = 0 ; i < n;i++)
109 {
110 tmp = get(stat,i);
111 if(tmp > ans)ans = tmp ;
112 }
113 printf("%d\n",ans);
114 }
115 }