本文主要是介绍DNA sequence HDU - 1560，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
点击打开链接
算是搜索进阶题吧（发现自己搜索要学的东西还很多啊 到现在才开始进阶。。）
枚举搜索深度（可二分） 看当前深度下是否可以解决问题
这道题目中还需要剪枝 若剩下所需匹配数大于剩余步数 则无解 提前返回
#include <bits/stdc++.h>
using namespace std;int len[10];
int n,lim,flag;
char dna[10][10];
char per[4];void dfs(int step,int* cur);
int judge(int* cur);int main()
{int num[10];int t,i;scanf("%d",&t);per[0]='A',per[1]='T',per[2]='C',per[3]='G';while(t--){scanf("%d",&n);for(i=0;i<n;i++){scanf("%s",dna[i]);len[i]=strlen(dna[i]);}lim=1,flag=0;while(1){memset(num,0,sizeof(num));dfs(1,num);if(flag==1) break;lim++;}printf("%d\n",lim);}return 0;
}void dfs(int step,int* cur)
{int num[10];int i,j;if(judge(cur)>lim-step+1) return;if(step==lim+1){flag=1;return;}for(i=0;i<4;i++){for(j=0;j<n;j++){if(cur[j]<len[j]&&dna[j][cur[j]]==per[i]){num[j]=cur[j]+1;}else{num[j]=cur[j];}}dfs(step+1,num);if(flag==1) return;}return;
}int judge(int* cur)
{int sum[4],maxx[4];int i,j;memset(maxx,0,sizeof(maxx));for(i=0;i<n;i++){memset(sum,0,sizeof(sum));for(j=cur[i];j<len[i];j++){if(dna[i][j]=='A'){sum[0]++;}else if(dna[i][j]=='T'){sum[1]++;}else if(dna[i][j]=='C'){sum[2]++;}else{sum[3]++;}}for(j=0;j<4;j++){maxx[j]=max(maxx[j],sum[j]);}}return maxx[0]+maxx[1]+maxx[2]+maxx[3];
}
这篇关于DNA sequence HDU - 1560的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
