1 #include <iostream> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cmath> 5 #include <cstdio> 6 #include <vector> 7 #include <algorithm> 8 #define LL long long 9 using namespace std;10 const int maxn = 20+10;11 const int INF = 1<<28;12 int n, len[maxn], add[maxn][maxn], ans;13 bool vis[maxn];14 char s[maxn][maxn];15 16 void cal(int a, int b, int lena, int lenb) //add计算串a在串b，前面增加的字符个数。17 {18     int i, j, k, f, x;19     for(i = 0; i < lena; i++)20     {21         f = 0;22         for(j = 0, k = i; j < lenb && k < lena; j++, k++)23         {24             if(s[a][k] == s[b][j]) continue;25             else { f = 1; break; }26         }27         if(f == 0) break;28     }29     x = lena - i;30     add[a][b] = lenb - x;31     if(add[a][b]<0) add[a][b] = 0;32 }33 void dfs(int pre, int sum, int lenth) //分别代表之前的串，和串的总数，总串的长度。34 {35     if(lenth >= ans) return;36     if(sum == n)37     {38         if(lenth < ans) ans = lenth;39         return;40     }41     for(int i = 0; i < n; i++)42     {43       if(!vis[i])44       {45           vis[i] = true;46           if(add[pre][i]==0) //一定要注意这是存在包含串，如abcdabc 包含 dab47           //串a包含串b，等价于从a到b的边等于0，那么这时，状态在转移时，在原本48           //是以串a结尾的状态加入串b，此时目标状态仍然是以串a结尾，这里需要注意。49           dfs(pre, sum+1, lenth+add[pre][i]);50           else51           dfs(i, sum+1, lenth+add[pre][i]);52           vis[i] = false;53       }54     }55 }56 int main()57 {58     int t, i, j;59     scanf("%d", &t);60     while(t--)61     {62         ans = INF;63         memset(add, 0, sizeof(add));64         memset(vis, false, sizeof(vis));65         scanf("%d", &n);66         for(i = 0; i < n; i++)67         {68             scanf("%s", s[i]);69             len[i] = strlen(s[i]);70         }71         for(i = 0; i < n; i++)72         for(j = 0; j < n; j++)73         cal(i, j, len[i], len[j]);74         for(i = 0; i < n; i++)75         {76             vis[i] = true;77             dfs(i, 1, len[i]);78             vis[i] = false;79         }80         printf("%d\n", ans);81     }82     return 0;83 }