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

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; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：Hdu1176免费馅饼	下一篇：C++ STL （标准模板库）精解

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: