hdu DNA sequence 疊代加深搜尋 已知n個字元串，求最小字元串使得這n個字元串是其子集

DNA sequence

Time Limit: 15000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 260    Accepted Submission(s): 114

Problem Description 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.

Input The first line is the test case number t. Then t test cases follow. In each case, the first line is an integer n ( 1<=n<=8 ) represents number of the DNA sequences. The following k lines contain the k sequences, one per line. Assuming that the length of any sequence is between 1 and 5.  

Output For each test case, print a line containing the length of the shortest sequence that can be made from these sequences.  

Sample Input

1
4
ACGT
ATGC
CGTT
CAGT
        

Sample Output

8
  
  
   #include<iostream>
   
#include<cstdio>
   
#include<string>
   
using namespace std;
   
int n;//字元串個數
   
string map[10];//字元串
   
int len[10];
   
string DNA="ATCG";
   
int DEPTH;//疊代加深搜尋深度
   
struct Point
   
{
   
    int p[10];
   
}Pos;//Pos.p[i]表示第i個字元串正在查詢的第Pos.p[i]個字元
   
int dfs(Point Pos,int cur)//cur表示目前位置
   
{
   
    if(cur>DEPTH) return 0;
   
    for(int i=0;i<n;i++)
   
    {
   
        if(len[i]-Pos.p[i]+cur>DEPTH) return 0;//剪枝
   
    }
   
    int flag=1;
   
    for(int i=0;i<n;i++)
   
    {
   
        if(Pos.p[i]<len[i])//表示還沒有都搜到最後位置
   
        {
   
            flag=0;break;
   
        }
   
    }
   
    if(flag) return 1;//表示都搜尋到了最後位置
   
    Point temp;
   
    for(int i=0;i<4;i++)//枚舉第cur位置上放的字元
   
    {
   
        flag=0;
   
        for(int j=0;j<n;j++)
   
        {
   
            if(map[j][Pos.p[j]]==DNA[i])
   
            {
   
                flag=1;
   
                temp.p[j]=Pos.p[j]+1;
   
            }
   
            else temp.p[j]=Pos.p[j];
   
        }
   
        if(flag)//剪枝
   
        {
   
            if(dfs(temp,cur+1)) return 1;
   
        }
   
    }
   
    return 0;//important
   
}
   
int main()
   
{
   
    int ci;scanf("%d",&ci);
   
    while(ci--)
   
    {
   
        scanf("%d",&n);
   
        int _max=0;
   
        for(int i=0;i<n;i++)
   
        {
   
            cin>>map[i];
   
            len[i]=map[i].size();
   
            if(len[i]>_max) _max=len[i];
   
        }
   
        for(int i=0;i<10;i++) Pos.p[i]=0;
   
        for(DEPTH=_max;;DEPTH++)
   
        {
   
            if(dfs(Pos,0)) break;
   
        }
   
        printf("%d/n",DEPTH);
   
    }
   
    return 0;
   
}