G - DNA sequence HDU - 1560

2-Day-G
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
题意：高中生物DNA序列好怀念，给出N个DNA序列，要求出一个包含这n个序列的最短序列是多长。

代码如下：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define clr(a,b) memset(a,b,sizeof(a));
using namespace std;</cstdio></algorithm></cstring></iostream>

bool flag=0;
char map[10][10],str[]="ACGT";
int point[10];
int num[10];
int n;

int estimation()
{
int ans=0;
for(int i=0;i<n;i++)
{
ans=max(ans,num[i]-point[i]);
}
return ans;
}

void dfs(int maxstep)
{
if(estimation()==0)
{
flag=true;
return;
}
if(maxstep<estimation())
{
return;
}
int repetition[10];
for(int i=0;i<n;i++)
repetition[i]=point[i];
int yes=0;
for(int i=0;i<4;i++)
{
for(int j=0;j<n;j++)
{
if(map[j][point[j]]==str[i])
{
yes=1;
point[j]++;
}
}
if(yes)
{
dfs(maxstep-1);
if(flag)
return;
for(int k=0;k<n;k++)
point[k]=repetition[k];
}

}

}

int main()
{
int t;
cin>>t;
while(t--)
{
cin>>n;
clr(point,0)
clr(num,0)
clr(map,'\0')
flag=0;
for(int i=0;i<n;i++)
{
scanf("%s",map[i]);
num[i]=strlen(map[i]);
}
int result=0;
for(int i=0;i<n;i++)
result=max(result,num[i]);
while(1)
{
dfs(result);
if(flag==true)
{
cout<<result<<endl;
break;
}
result++;
}
}
return 0;
}