poj1699

题目：给你一些序列，要求进行合并合并完最短。eg，AGCT与CTAA 可以合并成AGCTAA（CT相同）

思路：先进行预处理，处理出i串与j串合并完的程度。。

然后进行dp或者记忆化搜索

因为n很小，所以我们可以进行状态压缩

用一个　＜２＾１０的数来表示该字符串连接了没，所以

　　f[i][j]表示此时状态为J，最后一个放的是第I个的最短长度

f[i][j] = f[k][j + (1 <<k - 1)]+s[k] - len[i][k] ( i放过且k没放过,len[i][k],表示k接在相同字母数 )

 1 、*
 2    State：Accepted
 3    Time:2013-03-18 18:35:21
 4 */
 5 #include<iostream>
 6 #include<cstring>
 7 #include<cstdlib>
 8 #include<string>
 9 #include<cstdio>
10 #include<cmath>
11 #include<algorithm>
12 #define M 1 << 12
13 #define CLR(NAME) memset(NAME , 0 ,sizeof(NAME))
14 using namespace std;
15 const int Inf = 1010101;
16 char s[15][250];
17 int n, f[M][12], T , len[15][15], MX ,ln[150];
18 
19 void init(){
20      scanf("%d",&n);
21      MX = 1 << n;
22      for (int i = 1; i <= n; ++i){
23        scanf("%s",&s[i]);
24        ln[i] = strlen(s[i]);
25      }
26 }
27 
28 int  work_out(int a, int b){
29      int la , lb , LL;
30      la = strlen(s[a]);
31      lb = strlen(s[b]);
32      for (int i = 0; i < la; ++i )
33        {
34           LL = 0;
35           for (int j = 0; j < lb; ++j)
36             {
37               if (i + j >=  la) break;
38               if (s[a][i + j] == s[b][j]) ++LL;
39             }
40           if  (LL == la - i) return LL;
41        }
42      return 0;
43 }
44 
45 void solve(){
46      CLR(f);
47      CLR(len);
48      int opt;
49      for (int i = 1; i <= n; ++i)
50          for (int j = 1; j <= n; ++j)
51             if (i != j)
52             len[i][j] = work_out(i , j);
53      for (int i = 0; i < MX; ++i)
54          for (int j = 0; j <= n; ++j)
55              f[i][j] = Inf;
56      for (int i = 1; i <= n ; ++i)
57            f[1 << (i - 1)][i] = ln[i];
58 
59      for (int i = 0; i < MX; ++i)
60          for (int j = 1; j <= n; ++j)
61             if (1 << (j - 1) & i)
62               {
63                  if (f[i][j] == Inf) continue;
64                  for (int k = 1; k <= n; ++k)
65                    {
66                       if ((i & (1 << (k - 1))) != 0){
67                     //         printf("%d & 1<<%d = %d\n", i , k -1, i & 1 << (k - 1));
68                              continue;
69                       }
70                       opt = i | (1 << (k-1));
71                       f[opt][k] = min(f[opt][k],f[i][j] + ln[k] - len[j][k]);
72                    }
73 
74               }
75    /*  for (int i = 0; i < MX; ++i)
76          for (int j = 1; j <= n; ++j)
77             if (1 << (j - 1) & i  && f[i][j] != Inf)
78               printf("f[%d][%d] = %d\n",i , j ,f[i][j]);*/
79      int ans = Inf;
80      for (int i = 1; i <= n; ++i)
81        ans = min(ans, f[MX - 1][i]);
82      printf("%d\n",ans);
83 }
84 int main(){
85      scanf("%d",&T);
86      while (T--){
87           init();
88           solve();
89      }
90 }