Human Gene Functions(dp)

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int INF=1<<28;
 8 int score[220][220];
 9 void init()
10 {
11     score[‘A‘][‘C‘]=score[‘C‘][‘A‘]=-1;
12     score[‘A‘][‘G‘]=score[‘G‘][‘A‘]=-2;
13     score[‘A‘][‘T‘]=score[‘T‘][‘A‘]=-1;
14     score[‘A‘][‘-‘]=score[‘-‘][‘A‘]=-3;
15     score[‘C‘][‘G‘]=score[‘G‘][‘C‘]=-3;
16     score[‘C‘][‘T‘]=score[‘T‘][‘C‘]=-2;
17     score[‘C‘][‘-‘]=score[‘-‘][‘C‘]=-4;
18     score[‘G‘][‘T‘]=score[‘T‘][‘G‘]=-2;
19     score[‘G‘][‘-‘]=score[‘-‘][‘G‘]=-2;
20     score[‘T‘][‘-‘]=score[‘-‘][‘T‘]=-1;
21 }
22 int main()
23 {
24     int t,dp[120][120];
25     scanf("%d",&t);
26     init();
27     while(t--)
28     {
29         int len1,len2;
30         char s1[120],s2[120];
31         scanf("%d %s",&len1,s1+1);
32         scanf("%d %s",&len2,s2+1);
33         for (int i = 0; i <= len1; i++)
34         {
35             for (int j = 0; j <= len2; j++)
36             {
37                 dp[i][j] = -INF;
38             }
39         }
40         dp[0][0] = 0;
41         for (int i = 1; i <= len2; i++)
42         {
43             dp[0][i] = dp[0][i-1]+score[s2[i]][‘-‘];
44         }
45         for (int j = 1; j <= len1; j++)
46         {
47             dp[j][0] = dp[j-1][0]+score[s1[j]][‘-‘];
48         }
49         for (int i = 1; i <= len1; i++)
50         {
51             for (int j = 1; j <= len2; j++)
52             {
53                 if (s1[i]!=s2[j])
54                 {
55                     dp[i][j] = max(dp[i][j],dp[i-1][j-1]+score[s1[i]][s2[j]]);
56                     dp[i][j] = max(dp[i][j],
57                                    max(dp[i-1][j]+score[s1[i]][‘-‘],dp[i][j-1]+score[‘-‘][s2[j]]));
58                 }
59                 else
60                 {
61                     dp[i][j] = max(dp[i][j],dp[i-1][j-1]+5);
62                 }
63             }
64         }
65         printf("%d\n",dp[len1][len2]);
66     }
67     return 0;
68 }