hdu 1560 DNA sequence
#include <bits/stdc++.h> using namespace std; int n,deep; char c[10] = "ACGT"; struct node { char s[10]; int len; } a[10]; int pos[10];//记录第i个序列正在使用第几个位置 int get_h() { int ans = 0; for(int i = 1; i<=n; i++) ans = max(ans,a[i].len-pos[i]);//找出在当前情况下最长的未被匹配的长度围殴估测长度 return ans; } int dfs(int step) {//step为当前的深度 if(step+get_h()>deep)//估计函数剪枝,当前长度+估测的长度比deep还大的话，也就没有继续往下搜索的必要了 return 0; if(get_h() == 0) return 1; int i,j; int tem[10]; for(i = 0; i<4; i++) { int flag = 0; for(j = 1; j<=n; j++) tem[j] = pos[j];//先将pos保存起来,便于后面的回溯 for(j = 1; j<=n; j++) { if(a[j].s[pos[j]] == c[i]) { //当前这位符合，则该串的位置往后移一位 flag = 1; pos[j]++; } } if(flag) { //有符合的，则往下搜索 if(dfs(step+1)) return 1;//找到最终结果了 for(j = 1; j<=n; j++)//还原,回溯的思想 pos[j] = tem[j]; } } return 0; } int main() { //freopen("data.in", "r", stdin); int t,i,j,maxn; cin >> t; while(t--) { cin>>n; maxn = 0; for(i = 1; i<=n; i++) { cin>>a[i].s; a[i].len = strlen(a[i].s); maxn = max(maxn,a[i].len); pos[i] = 0; } deep = maxn;//显然搜索的深度至少为maxn for(; ; ++deep){//一点一点的增加深度 if(dfs(0))break; } cout << deep << endl; } return 0; }