本文主要是介绍HDU 1568 DNA sequence（迭代深搜），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1560
这种做法还是第一次，不过这里的搜索思想还是和以前基本上相同的，迭代深搜关键还是迭代，其实也不难理解
这个题目的搜索如果不限制深度的话可能就是一个无穷无尽的搜索，所以一定要我们来认为加入一个条件让其退出
搜索，所以就从可能的答案的最小向上迭代搜索，搜索到第一个就是题目答案！
不谈迭代这个题目的搜索思想也是绝对经典的！
pos[i]表示的是第i（从第0开始）个串已经存在子系列在当前找到的串中子系列的长度
get_max函数计算的就是最少还需要多长才能满足要求，如果当前要求最短的长度都
超过迭代的值的话就说名这次迭代失败，不可能答案是deepth的值！
仔细分析下程序就明白了，说还不怎么能说清楚！
#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
using namespace std;
#define MAX(a,b) (a>b?a:b)
struct point{char str[10];int length;
}po[10];
int pos[10],n,deepth;
const char *dir="ACGT";
int get_max(){int ans=0;for(int i=0;i<n;i++){ans=MAX(ans,po[i].length-pos[i]);}return ans;
}
bool dfs(int deep){int temp=get_max();if(temp+deep > deepth) return false;if(temp==0) return true;bool flag=false;for(int i=0;i<4;i++){int tem[10];flag=false;memcpy(tem,pos,sizeof(pos));for(int j=0;j<n;j++){if(po[j].str[pos[j]]==dir[i]){flag=true;pos[j]++;}}if(flag){if(dfs(deep+1)) return true;memcpy(pos,tem,sizeof(tem));}}return false;
}
int main(){int i,j,k,t,Max;scanf("%d",&t);while(t--){Max=0;scanf("%d",&n);for(i=0;i<n;i++){scanf("%s",po[i].str);po[i].length=strlen(po[i].str);Max=MAX(Max,po[i].length);}memset(pos,0,sizeof(pos));deepth=Max;while(!dfs(0)) deepth++;printf("%d\n",deepth);}return 0;
}
这篇关于HDU 1568 DNA sequence（迭代深搜）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
