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;
}