这题其实是由bug的 一个串包含其它两个串的数据没有 所以就这么水了它吧 只处理两个串的关系就行了
回来补点。。看了huge的博客 发现其实不是有Bug 题意没读清楚 必须首尾相连 像AGCT GC这样就不算。。降低了复杂
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
#define INF 0x3f3f3f
char s[][];
int k[],o[][],n;
int vis[],ans;
void init()
{
int i,j;
for(i = ; i <= n ; i++)
{
for(j = ; j <= n ; j++)
{
if(i==j)
continue;
o[i][j] = ;
for(int g = ; g < k[i] ; g++)
{
if(s[j][]==s[i][g])
{
int k1 = ,k2 = g+;
while(k1<k[i]&&k2<k[j]&&s[j][k1]==s[i][k2])
{
k1++;
k2++;
}
if(k1==k[i]||k2==k[j])
{
o[i][j] = k1;
break;
}
}
}
}
}
}
void dfs(int x,int v,int sum)
{
if(sum>ans)
return ;
if(v==n)
{
ans = sum;
return ;
}
int i;
for(i = ; i <= n ; i++)
{
if(!vis[i])
{
vis[i] = ;
sum+=(k[i]-o[x][i]);
dfs(i,v+,sum);
sum-=(k[i]-o[x][i]);
vis[i] = ;
}
}
}
int main()
{
int i,t;
scanf("%d",&t);
while(t--)
{
memset(vis,,sizeof(vis));
ans = INF;
scanf("%d%*c",&n);
for(i = ; i <= n ;i++)
{
scanf("%s",s[i]);
k[i] = strlen(s[i]);
}
init();
for(i = ; i <= n ;i++)
{
vis[i] = ;
dfs(i,,k[i]);
vis[i] = ;
}
printf("%d\n",ans);
}
return ;
}