poj1699:http://poj.org/problem?id=1699
题意：给你nge串，让你求出这些串组成的最小的串重叠部分只算一次。
题解：我的做法是DFS，因为数据范围只有10，就算是n！也只有300多万，加上剪枝，就可以过了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
char str[][],s[];
int ans;
bool vis[];
int getlen(char s1[],char s2[],int l1,int l2){
int ans;//表示重叠部分的长度
if(l1>=l2){
for(ans=l2;ans>=;ans--){
bool flag=true;
for(int i=;i<ans;i++){
if(s2[i]!=s1[l1-(ans-i)]){
flag=false;
break;
}
}
if(flag)return ans;
}
}
else{
for(ans=l1;ans>=;ans--){
bool flag=true;
for(int i=;i<ans;i++){
if(s2[i]!=s1[l1-(ans-i)]){
flag=false;
break;
} }
if(flag)return ans;
}
}
}
void DFS(char fa[],int ll,int dep){
if(ll>=ans)return;
if(dep==n){
ans=min(ll,ans);
return;
}
for(int i=;i<=n;i++){
if(vis[i])continue;
int tt=strlen(str[i]);
int temp=getlen(fa,str[i],ll,tt);
for(int j=ll;j<ll+(tt-temp);j++){
fa[j]=str[i][temp+(j-ll)];
}
vis[i]=;
DFS(fa,ll+tt-temp,dep+);
vis[i]=;
}
}
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
memset(str,,sizeof(str));
memset(s,,sizeof(s));
memset(vis,,sizeof(vis));
ans=;
for(int i=;i<=n;i++){
scanf("%s",str[i]);
}
for(int i=;i<=n;i++){
memset(s,,sizeof(s));
strcpy(s,str[i]);
vis[i]=;
DFS(s,strlen(str[i]),);
vis[i]=;
}
printf("%d\n",ans);
} }