HDU - 1560 DNA sequence

给你最多8个长度不超过5的DNA系列,求一个包含所有系列的最短系列。

迭代加深的经典题。(虽然自己第一次写)

定一个长度搜下去,搜不出答案就加深大搜的限制,然后中间加一些玄学的减枝

//Twenty
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
int ans,T,n,sz[],maxn,lim;
char s[][],b[]={'A','T','C','G'};
void dfs(int cnt,int len[]) {
if(cnt>lim) return;
int maxx=;
for(int i=;i<=n;i++)
maxx=max(maxx,sz[i]-len[i]);
if(maxx==) {
ans=cnt;
return;
}
if(cnt+maxx>lim) return;
for(int i=;i<;i++) {
int tep[];
int flag=;
for(int j=;j<=n;j++) {
if(s[j][len[j]]==b[i]) {
tep[j]=len[j]+;
flag=;
}
else tep[j]=len[j];
}
if(flag) dfs(cnt+,tep);
if(ans!=-) break;
}
}
int main()
{
scanf("%d",&T);
while(T--) {
scanf("%d",&n);
maxn=;
for(int i=;i<=n;i++) {
scanf("%s",s[i]);
sz[i]=strlen(s[i]);
maxn=max(maxn,sz[i]);
}
for(;;) {
ans=-;
lim=maxn;
int p[]={};
dfs(,p);
if(ans!=-) break;
maxn++;
}
printf("%d\n",ans);
}
return ;
}
上一篇:用Spring Tools Suite(STS)开始一个RESTful Web Service


下一篇:java基础之:详解内部类(转载)