意甲冠军：看图片是晶莹剔透的，正确的， N连接到第一序列（同样的序列部分）。总序列获得最短。
主题链接：http://poj.org/problem?id=1699
~~~~
思路就是：将N个序列首尾相连能重合的长度求粗来。
然后DFS枚举每种首尾相连的情况。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 22
#define INF 0x7fffffff
using namespace std; int n,ans;
int f[N][N],vis[N],len[N];
char str[N][N];
void get(int x,int y) //f[x][y],将y贴到x后面能降低的最大反复长度
{
int i,j,l;
for(l=len[y];l>0;l--) //枚举长度
{
int ok=1;
for(i=len[x]-l,j=0;i<len[x] && j<len[y];i++,j++)
{
if(i<0) //~~
{
ok=0;
break;
}
if(str[x][i]!=str[y][j])
{
ok=0;
break;
}
}
if(ok)
{
f[x][y]=l;
return ;
}
}
f[x][y]=0;
}
void dfs(int x,int s,int tot)
{
if(s==n)
{
ans=min(ans,tot);
return ;
}
if(tot>ans) //剪枝~
return ;
for(int i=0;i<n;i++)
{
if(!vis[i])
{
vis[i]=1;
dfs(i,s+1,tot+len[i]-f[x][i]); //~~
vis[i]=0;
}
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%s",str[i]);
len[i]=strlen(str[i]);
}
memset(f,0,sizeof(f));
memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(i==j) continue;
else get(i,j);
}
}
ans=INF;
for(int i=0;i<n;i++) //dfs枚举每种首尾相连的方法。 {
vis[i]=1;
dfs(i,1,len[i]);
vis[i]=0;
}
printf("%d\n",ans);
}
return 0;
}
版权声明：本文博主原创文章，博客，未经同意不得转载。