POJ 1699 kmp+枚举

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<algorithm>
 6 using namespace std;
 7 
 8 const int inf=0x3fffffff;
 9 const int maxn=11;
10 char str[maxn][21];
11 int cost[maxn][maxn];
12 int len[maxn];
13 int n,t;
14 
15 int cal(char *st1, char *st2)
16 {
17     int len1 = strlen(st1);
18     int len2 = strlen(st2);
19     for (int i = len1 - len2; i < len1; i++)
20     {
21         bool ok = true;
22         for (int j = i; j < len1; j++)
23             if (st1[j] != st2[j - i])
24             {
25                 ok = false;
26                 break;
27             }
28         if (ok)
29             return len2 + i - len1;
30     }
31     return len2;
32 }
33 void work()
34 {
35     for(int i=0;i<n;i++)
36         for(int j=0;j<n;j++)
37     {
38         cost[i][j]=cal(str[i],str[j]);
39     }
40 }
41 int Get_ans()
42 {
43     int next[maxn];int ans=inf,sum;
44     for(int i=0;i<n;i++) next[i]=i;
45     do{
46         sum=len[next[0]];
47         for(int i=0;i<n-1;i++)
48         {
49             sum+=cost[next[i]][next[i+1]];
50         }
51          ans=min(ans,sum);
52         }while(next_permutation(next,next+n));
53         return ans;
54 }
55 int main()
56 {
57     //freopen("in.txt","r",stdin);
58     scanf("%d",&t);
59     while(t--){
60             memset(str,0,sizeof(str));
61             scanf("%d",&n);
62             for(int i=0;i<n;i++)
63             {
64                 scanf("%s",str[i]);
65                 len[i]=strlen(str[i]);
66             }
67             work();
68             int ans=Get_ans();
69             printf("%d\n",ans);
70     }
71     return 0;
72 }