hdu 1560 DNA sequence（IDA*）

 

 

DNA sequence

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

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
Source HDU 2006-12 Programming Contest
Recommend LL | We have carefully selected several similar problems for you: 1667 1043 1813 1226 1401
題目大意：給n個序列，找到一個包含所有給出序列的最短長度並輸出。 解題思路：采用gei_h()得到當前狀態下最長的未匹配的長度。在進行深度搜索。每個串的長度不超過5，最多只有8個序列，所以IDA不超過40次。
詳見代碼。

#include 
#include 
#include 
#include 

using namespace std;

int n;
char ch[10][10];
int len[10],want;
char dir[10]= {'A','C','G','T'};
int wei[10];//記錄第i個序列正在使用第幾個位置

int get_h()
{
    int t=0;
    for (int i=1; i<=n; i++)
    {
        t=max(t,len[i]-wei[i]);//得到當前情況下最長的未被匹配的長度
    }
    return t;
}

int IDA(int dep)
{
    if(dep+get_h()>want)//當前長度+估測的長度比我想要的還大的話，就不必繼續搜索
    {//cout<Max)
                Max=len[i];
        }
        memset(wei,0,sizeof(wei));
        want=Max;//從最長序列開始查找
        while (1)
        {
            if (IDA(0))
            {
                break;
            }
            want++;
        }
        printf ("%d\n",want);
    }
    return 0;
}