﻿HDU 1560 DNA sequence(DFS(IDA*))-Ocrosoft

# DNA sequence

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

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

```

Author
LL

Solution

```#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <list>
#include <stack>
#include <string>
#include <vector>
#include <cstring>
#include <cctype>
#include <queue>
#include <set>
#define ms(a) memset(a,0,sizeof(a))
using namespace std;
template <typename T>
{
{
T tt;
cin>>tt;
return tt;
}
cin>>t;
return t;
}
int n,pos[10],deep;
char c[]="ACGT";
vector<string> v;
int get_h()//估值函数
{
int ans=0;
for(int i=0; i<n; i++)
ans=max(ans,(int)(v[i].size()-pos[i]));
return ans;
}
bool dfs(int step)
{
if(step+get_h()>deep)return 0;
if(!get_h())return 1;//返回值为0，没有可以匹配的，结束。
int t[10];
for(int i=0; i<4; i++)
{
int f=0;
memcpy(t,pos,sizeof(pos));
for(int j=0; j<n; j++)
if(v[j][pos[j]]==c[i])
f=1,pos[j]++;
if(f)
{
if(dfs(step+1))return 1;
memcpy(pos,t,sizeof(t));
}
}
return 0;
}
int main()
{
int N;
cin>>N;
while(N--)
{
cin>>n;
string s;
v.clear();
ms(pos);
int maxx=0;
for(int i=0; i<n; i++) //读入并记录最大长度