動態規劃練習題 相似基因 gene 題解

問題描述

大家都知道，基因可以看作一個鹼基對序列。它包含了 4 種核苷酸，簡記作 A,C,G,T 。生物學家正致力於尋找人類基因的功能，以利用於診斷疾病和發明藥物。

在一個人類基因工作組的任務中，生物學家研究的是：兩個基因的相似程度。因為這個研究對疾病的治療有著非同尋常的作用。兩個基因的相似度的計算方法如下：

對於兩個已知基因，例如 AGTGATG 和 GTTAG ，將它們的鹼基互相對應。當然，中間可以加入一些空鹼基 - ，例如：

A	G	T	G	A	T	-	G
-	G	T	-	-	T	A	G

這樣 , 兩個基因之間的相似度就可以用鹼基之間相似度的總和來描述，鹼基之間的相似度如下表所示：

那麼相似度就是： (-3)+5+5+(-2)+(-3)+5+(-3)+5=9 。因為兩個基因的對應方法不唯一，例如又有：

A	G	T	G	A	T	G
-	G	T	T	A	-	G

相似度為： (-3)+5+5+(-2)+5+(-1)+5=14 。規定兩個基因的相似度為所有對應方法中，相似度最大的那個。

輸入

共兩行。每行首先是一個整數，表示基因的長度；隔一個空格後是一個基因序列，序列中只含 A,C,G,T 四個字母。 1<= 序列的長度 <=100 。

輸出

僅一行，即輸入基因的相似度。

樣例

gene.in

7 AGTGATG

5 GTTAG

gene.out

14

【分析】

簡單的動態規劃。

【我的代碼】

裸代碼RawCode

C++语言: Codee#25681

01 /*
02 *Problem: 相似基因 gene
03 *Author: Yee-fan Zhu
04 *Method: Dynamic Programming
05 *Email: zyfworks@gmail.com
06 */
07 #include <cstdio>
08 #include <cstdlib>
09 #include <cstring>
10 #define openfile(str) freopen(str".in","r",stdin),freopen(str".out","w",stdout)
11 using namespace std;
12 const int MAXN=101;
13 /*
14 *A:1 C:2 G:3 T:4 -:5
15 */
16 int Sml[6][6]={
17 {0,0,0,0,0},
18 {0,5,-1,-2,-1,-3},
19 {0,-1,5,-3,-2,-4},
20 {0,-2,-3,5,-2,-2},
21 {0,-1,-2,-2,5,-1},
22 {0,-3,-4,-2,-1,-100000},
23 };
24
25 int GetNum(char c)
26 {
27     if(c=='A') return 1;
28     if(c=='C') return 2;
29     if(c=='G') return 3;
30     if(c=='T') return 4;
31     return 5;
32 }
33
34 char str1[MAXN],str2[MAXN];
35 int F[MAXN][MAXN];
36 int len1,len2;
37 void init()
38 {
39     scanf("%d %s\n%d %s\n",&len1,&str1,&len2,&str2);
40     for(int i=len1;i>=1;i--) str1[i]=str1[i-1];
41     for(int i=len2;i>=1;i--) str2[i]=str2[i-1];
42     str1[0]='0',str2[0]='0';
43     for(int i=1;i<=len1;i++)
44         for(int j=1;j<=len2;j++)
45             F[i][j]=0;
46     for(int i=1;i<=len1;i++) F[i][0]=F[i-1][0]+Sml[GetNum(str1[i])][5];
47     for(int i=1;i<=len2;i++) F[0][i]=F[0][i-1]+Sml[5][GetNum(str2[i])];
48 }
49
50 int MAX(int a,int b)
51 {
52     return a>b?a:b; 
53 }
54
55 int main()
56 {
57     openfile("gene");
58     init();
59     for(int i=1;i<=len1;i++)
60     {
61         for(int j=1;j<=len2;j++)
62         {
63             F[i][j]=F[i-1][j-1]+Sml[GetNum(str1[i])][GetNum(str2[j])];
64             F[i][j]=MAX(F[i][j],F[i-1][j]+Sml[GetNum(str1[i])][5]);
65             F[i][j]=MAX(F[i][j],F[i][j-1]+Sml[5][GetNum(str2[j])]);   
66         }
67     }
68     printf("%d\n",F[len1][len2]);
69     return 0;   
70 }