POJ1080

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <string.h>
 4 using namespace std;
 5 char a[105],b[105];
 6 int dp[105][105];
 7 char s[8]="ACGT-";
 8 int score[5][5]={
 9     { 5, -1, -2, -1, -3 },
10     { -1, 5, -3, -2, -4 },
11     { -2, -3, 5, -2, -2 },
12     { -1, -2, -2, 5, -1 },
13     { -3, -4, -2, -1, 0 }
14 };
15 int getn(char c){
16     for(int i=0;i<5;i++){
17         if(s[i]==c)return i;
18     }
19 }
20 int main(){
21     int t,x,y;
22     scanf("%d",&t);
23     while(t--){
24         scanf("%d",&x);
25         scanf("%s",a+1);
26         scanf("%d",&y);
27         scanf("%s",b+1);
28         dp[0][0]=0;
29         for(int i=1;i<=x;i++)dp[i][0]=score[getn(a[i])][4]+dp[i-1][0];
30         for(int i=1;i<=y;i++)dp[0][i]=score[4][getn(b[i])]+dp[0][i-1];
31         for(int i=1;i<=x;i++){
32             for(int j=1;j<=y;j++){
33                 int temp1=dp[i-1][j-1]+score[getn(a[i])][getn(b[j])];                //相当于LCS的a[i]=b[j];
34 
35                 int temp2=dp[i][j-1]+score[4][getn(b[j])];                            //相当于    a[i]    ‘-‘        匹配
36                                                                                     //            b[j-1]    b[j]
37 
38                 int temp3=dp[i-1][j]+score[getn(a[i])][4];                            //相当于    a[i-1]    a[i]    匹配
39                                                                                     //            b[jj]    ‘-‘
40                 dp[i][j]=max(temp1,max(temp2,temp3));
41             }
42         }
43         printf("%d\n",dp[x][y]);
44     }
45     return 0;
46 }