judge函数没写好，直接暴力就可以水过去。
1 #include <cstring> 2 #include <cstdio> 3 #include <string> 4 #include <iostream> 5 #include <algorithm> 6 #include <vector> 7 #include <queue> 8 using namespace std; 9 char str[21][31]; 10 int p[21][21]; 11 int len[21]; 12 int o[21],minz,n; 13 int judge(int x,int y) 14 { 15 int len1,len2,i,j,k,ans,minz,flag; 16 len1 = strlen(str[x]); 17 len2 = strlen(str[y]); 18 minz = min(len1,len2); 19 ans = 0; 20 for(k = 1;k <= minz;k ++) 21 { 22 flag = 1; 23 for(i = 0,j = len1-k;i < k;i ++,j ++) 24 { 25 if(str[x][j] != str[y][i]) 26 { 27 flag = 0; 28 break; 29 } 30 } 31 if(flag) ans = k; 32 } 33 return len2-ans; 34 } 35 void dfs(int x,int step,int sum) 36 { 37 int i; 38 if(step >= minz) 39 return ; 40 if(sum == n) 41 { 42 minz = min(minz,step); 43 return ; 44 } 45 for(i = 1;i <= n;i ++) 46 { 47 if(!o[i]) 48 { 49 o[i] = 1; 50 dfs(i,step+p[x][i],sum+1); 51 o[i] = 0; 52 } 53 } 54 } 55 int main() 56 { 57 int i,t,j; 58 scanf("%d",&t); 59 while(t--) 60 { 61 scanf("%d",&n); 62 memset(o,0,sizeof(o)); 63 minz = 0; 64 for(i = 1;i <= n;i ++) 65 { 66 scanf("%s",str[i]); 67 len[i] = strlen(str[i]); 68 minz += len[i]; 69 } 70 for(i = 1;i <= n;i ++) 71 { 72 for(j = 1;j <= n;j ++) 73 { 74 if(i != j) 75 { 76 p[i][j] = judge(i,j); 77 } 78 } 79 } 80 for(i = 1;i <= n;i ++) 81 { 82 o[i] = 1; 83 dfs(i,len[i],1); 84 o[i] = 0; 85 } 86 printf("%d ",minz); 87 } 88 return 0; 89 }