The twenty-first century is a biology-technology developing century. We know that a gene is made of DNA. The nucleotide bases from which DNA is built are A(adenine), C(cytosine), G(guanine), and T(thymine). Finding the longest common subsequence between DNA/Protein sequences is one of the basic problems in modern computational molecular biology. But this problem is a little different. Given several DNA sequences, you are asked to make a shortest sequence from them so that each of the given sequence is the subsequence of it.

For example, given "ACGT","ATGC","CGTT" and "CAGT", you can make a sequence in the following way. It is the shortest but may be not the only one.

1

4

ACGT

ATGC

CGTT

CAGT

8

思路
如果DNA最长的串长度为n,那就先搜索以n为长度，是否存在符合条件的母串，若不存在，再搜索n+1；
这便是所谓的迭代加深搜索。结束。
代码中用到的maxx，只是一个剪枝而已。

#include<iostream>

#include<algorithm>

#include<vector>

#include<stack>

#include<queue>

#include<map>

#include<set>

#include<cstdio>

#include<cstring>

#define fuck(x) cout<<#x<<" = "<<x<<endl;

#define ls (t<<1)

#define rs ((t<<1)+1)

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int maxn = ;

const int inf = 2.1e9;

const ll Inf = ;

const int mod = 1e9+;

const double eps = 1e-;

char s[][];

int maxs=;

int tot[];

int n,pos[];

char a[]="ACGT";

void view()

{

    for(int i=;i<=n;i++){

        cout<<pos[i]<<" ";

    }

    cout<<endl;

}

bool dfs(int t)

{

    int maxx=;

    for(int i=;i<=n;i++){

        maxx=max(maxx,tot[i]-pos[i]);

    }

    if(maxx==){return true;}

    if(t+maxx>maxs){return false;}

    bool vis[];

    for(int i=;i<;i++){

        memset(vis,,sizeof(vis));

        for(int j=;j<=n;j++){

            if(s[j][pos[j]]==a[i]){

                pos[j]++;

                vis[j]=true;

            }

        }

        if(dfs(t+)){return true;}

        for(int j=;j<=n;j++){

            if(vis[j]){

                pos[j]--;

            }

        }

    }

    return false;

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--){

        scanf("%d",&n);

        maxs=;

        for(int i=;i<=n;i++){

            scanf("%s",s[i]);

            tot[i]=strlen(s[i]);

            maxs=max(maxs,tot[i]);

        }

        while(true){

            memset(pos,,sizeof(pos));

            if(dfs()){

                printf("%d\n",maxs);

                break;

            }

            else maxs++;

        }

    }

    return ;

}