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;
}
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
