浙江财经大学
信息管理与工程学院

HDU 1560 DNA sequence(DFS(IDA*))

本文由 Ocrosoft 于 2016-07-12 10:26:24 发表

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

虽然不知道IDA*是什么,但是听着很厉害的样子。能找到最优解又避免了BFS的空间浪费。

题意:给出一些串,要求找最短的公共子序列。输出那个序列的长度。

#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 read(T& t,bool readOnly=0)
{
    if(readOnly)
    {
        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++) //读入并记录最大长度
            v.push_back(read(s)),maxx=max(maxx,(int)s.size());
        deep=maxx;
        while(!dfs(0))deep++;//直到找到答案
        printf("%d\n",deep);
    }
    return 0;
}

 

欢迎分享与转载,请保留链接与出处。Ocrosoft » HDU 1560 DNA sequence(DFS(IDA*))

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址