http://poj.org/problem?id=1699
题目大意：
给你n个字符串 可以让他们任意首尾合并相连
求包含所以字符串的最短总字符串长度
注意：
只能首尾合并相连 像 ACTG 和 CT 是不可以的
思路：
求出所以成对字符串合并会增加多少长度 并记录在表中
然后Dfs搜索就可以啦 剪枝效果更好
代码及其注释：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<algorithm>
#include<set>
using namespace std;
const int N=11;
char s[N][N*2];
int l[N];
int addl[N][N];
bool had[N];
int ans, n;
void Findaddl(int I,int J)
{
int w,i,j;
for(w=max(0,l[I]-l[J]);w<l[I];++w)
{
for(i=w,j=0;j<l[J]&&i<l[I];++j,++i)
{
if(s[I][i]!=s[J][j])
break;
}
if(j==l[J]||i==l[I])
break;
}
if(j==l[J])
addl[I][J]=0;
else
addl[I][J]=w+l[J]-l[I];
}
void Dfs(int sum,int Len,int pre)
{
for(int i=0;i<n;++i)
{
if(!had[i])
{
had[i]=true;
if(sum==n)
{
ans=min(ans,Len+addl[pre][i]);//枚举最小 答案
}
else if(Len+addl[pre][i]<ans)//剪枝
{
Dfs(sum+1,Len+addl[pre][i],i);
}
had[i]=false;
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
getchar();
ans=0;
for(int i=0;i<n;++i)
{
gets(s[i]);
l[i]=strlen(s[i]);//求长度
ans+=l[i];//记录长度和 这个和是最大长度可能
}
for(int i=0;i<n;++i)
{
for(int j=0;j<n;++j)
{
if(i!=j)
Findaddl(i,j);//求i 和 j 首尾合并增加多少长度
}
}
memset(had,false,sizeof(had));
for(int i=0;i<n;++i)
{
had[i]=true;
Dfs(2,l[i],i);//深搜
had[i]=false;
}
printf("%d\n",ans);
}
return 0;
}
