http://acm.hdu.edu.cn/showproblem.php?pid=1560

DNA sequence

Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 732 Accepted Submission(s): 356

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

ACGT
ATGC

CGTT

CAGT

Sample Output

Author

参照大神代码优化hash标记节省时间1S以上，碉堡了：

有图有真相：

代码：

 #include<iostream>

 #include<stdio.h>

 #include<string.h>

 #include<queue>

 #define M 1679616+100000

 using namespace std;

 struct Nod

 {

     int st;

     int ln;

 }nd1,nd2;

 int hash[M];

 int n,len[],size,maks;

 char str[][];

 char ku[] ="ACGT";

 int cas =;  // hash标记用，这里可以节省大量初始化时间（大神专用，哈哈，看的大神代码都这么玩的）

 int bfs()

 {

     int pos[];

     queue<Nod> q;

     nd1.st = ;

     nd1.ln = ;

     q.push(nd1);

    // memset(hash,0,sizeof(hash));   //用上面的cas代替初始化过程，节省时间1s以上

     while(!q.empty())

     {

         nd2 = q.front();

         q.pop();

         int i,j;

         int st = nd2.st;

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

         {

             pos[i] = st%maks;

             st/=maks;

         }

         for(j=;j<;j++)

         {

             st = ;

             for(i=n-;i>=;i--)

             {

                 st = st * maks + pos[i] + (str[i][pos[i]] == ku[j]);

             }

             if(hash[st] == cas)    continue;

             if(st == size)    return nd2.ln + ;

             hash[st] = cas;

             nd1.ln = nd2.ln + ;

             nd1.st = st;

             q.push(nd1);

         }

     }

     return -;

 }

 int main()

 {

     int t;

     scanf("%d",&t);

     cas = ;

     while(t--)

     {

         scanf("%d",&n);

         int i;

         maks=;

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

         {

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

             len[i] = strlen(str[i]);

             if(maks<len[i]) maks = len[i];

         }

         maks++;

         size = ;

         for(i=n-;i>=;i--) size = size*maks+len[i];

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

         cas++;  //cas加1，用来标记下一组测试数据

     }

     return ;

 }

巴特西

hdu 1560 DNA sequence(搜索)

DNA sequence

最新文章

热门文章