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元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
