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.
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
ATGC
CGTT
CAGT
Sample Output
8
Author
LL
参照大神代码优化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 ;
}