搜索进阶------E - DNA sequence
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
看到这道题目时,不知道怎么做,以为这要搜索,按照图中的方法这样构造不就是最短吗,但其实不是这样的,应该是n个序列的排列,然后这样构造,取最短,这样时间可能会超,我也没尝试。。。
如果遍历所有的序列(每一位都有四个选择ATCG地遍历下去),因为这不知道搜索的深度, 如果搜索不到就继续往下搜索,会爆栈的,所以可以用迭代加深搜索,一个深度一个深度地尝试,如果在当前深度找到一个解,这个深度就是最小长度。。
还有一个最重要的剪枝,就是当前深度 + 剩下每个单个字符串未匹配的最长长度 > deep,就返回
因为当前深度 + 至少还需要多少深度 > deep表示之后必找不到一个解,直接返回即可
不加这个剪枝会超
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<cmath>
using namespace std;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 5;
int deep,n,t;
char a[] = "ACGT";
char s[10][10];
int pos[10];
int calmax()
{
int MAX = 0;
for(int i = 0;i < n;++i)
MAX = max(MAX,(int)(strlen(s[i]) - pos[i]));
return MAX;
}
bool dfs(int index)
{
int k = calmax();
if(k == 0) return true;
if(k + index > deep) return false;
for(int i = 0;i < 4;++i)
{
int tmp[10];
for(int j = 0;j < n;++j)
tmp[j] = pos[j];
bool flag = false;
for(int j = 0;j < n;++j)
{
if(s[j][pos[j]] == a[i]){
pos[j]++;
flag = true;
}
}
if(flag){
if(dfs(index + 1)) return true;
for(int j = 0;j < n;++j)
pos[j] = tmp[j];
}
}
return false;
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
deep = 0;
for(int i = 0;i < n;++i)
{
scanf("%s",s[i]);
deep = max(deep,(int)(strlen(s[i])));
}
memset(pos,0,sizeof(pos));
//如果不确定深度的搜索,而且是暴力的遍历所有可能序列,这个dfs写不出来
//就会AAAAA....一直递归到栈爆掉
//但是如果一个深度一个深度地去尝试,那么在这个深度找到的必定是最短的长度序列
//cout << deep << endl;
while(true)
{
if(dfs(0)) break;
//cout << deep << endl;
deep++;
}
printf("%d\n",deep);
}
return 0;
}