程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 1560DNA sequence

HDU 1560DNA sequence

編輯：C++入門知識

HDU 1560DNA sequence

DNA sequence

Time Limit : 15000/5000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 8 Accepted Submission(s) : 1

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

Author LL
Source HDU 2006-12 Programming Contest

找到最短的DNA序列其子序列包含題意所給的DNA

IDA* 估價函數為最長剩余DNA數量

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define inf 1<<30
#define LL long long
#define maxn 1<<24
using namespace std;
char str[10][10];//保存DNA
int l[10];
int t,n;
int tlen;
bool flag;

int get_h(int * a)  //估價函數
{
    int ans=0;
    for(int i=0; ilen) return ;//預估值小於最優估計值

    if(len==0)  //找到序列
    {
        flag=true ;
        return  ;
    }

    bool vis[10];
    memset(vis,false ,sizeof(vis));
    for(int i=0; i