HDU 1560 DNA sequence DFS
题意：找到一个最短的串，使得所有给出的串是它的子序列，输出最短的串的长度，然后发现这个串最长是40
分析：从所给串的最长长度开始枚举，然后对于每个长度，暴力深搜，枚举当前位是哪一个字母，注意剪枝
注：然后我看网上都说这叫迭代加深搜索
#include <iostream> #include <cstdio> #include <vector> #include <cstring> #include <algorithm> #include <string> #include <cmath> #include <queue> #include <set> using namespace std; struct Node { int len; char s[8]; } o[10]; char c[5]="AGCT"; int pos[10],T,n,deep; int check() { int ans=0; for(int i=1; i<=n; ++i) ans=max(ans,o[i].len-pos[i]); return ans; } bool dfs(int step) { if(step+check()>deep)return 0; if(!check())return 1; int tmp[10]; for(int i=1; i<=n; ++i) tmp[i]=pos[i]; for(int i=0; i<4; ++i) { bool flag=0; for(int j=1; j<=n; ++j) { if(o[j].s[pos[j]]==c[i]) { pos[j]++; flag=1; } } if(flag) { if(dfs(step+1))return 1; for(int i=1;i<=n;++i) pos[i]=tmp[i]; } } return 0; } int main() { scanf("%d",&T); while(T--) { scanf("%d",&n); int mx=0; for(int i=1; i<=n; ++i) { scanf("%s",o[i].s); o[i].len=strlen(o[i].s); mx=max(mx,o[i].len); } memset(pos,0,sizeof(pos)); deep=mx; for(;;++deep) if(dfs(0))break; printf("%d ",deep); } return 0; }