dp[i][j]=max(  max( max(dp[i-1][j]+map[s[i]]['-'],     d[i][j-1]+map['-'][ss[j]])

,

dp[i-1][j-1]+map[s[i]][ss[j]]

)

,

dp[i][j]

);

 

1 #include
      
        2 #include
       
         3 #include
        
          4 int map[6][6]={ 5       0,0,0,0,0,0, 6       0,5,-1,-2,-1,-3, 7       0,-1,5,-3,-2,-4, 8       0,-2,-3,5,-2,-2, 9        0,-1,-2,-2,5,-1,10       0,-3,-4,-2,-1,-10000011 };12 int fun(char ch)13 {14     if(ch=='A')return 1;15     if(ch=='C')return 2;16     if(ch=='G')return 3;17     if(ch=='T')return 4;18     return 5;19 }20 int Max(int x,int y)21 {22     return x>y?x:y;23 }24 int main()25 {26     int t,n,m,dp[110][110];27     28     int i,j,k,a,b,c;29     char s1[110],s2[110];30     scanf("%d",&t);31     while(t--)32     {33         scanf("%d %s",&n,s1+1);34         scanf("%d %s",&m,s2+1);35         memset(dp,0,sizeof(dp));36         for(i=1;i<=n;i++)37         {38             a=fun(s1[i]);39             b=fun('-');40             dp[i][0]=dp[i-1][0]+map[a][b];41                 42         }43     44         for(j=1;j<=m;j++)45         {46             a=fun('-');47             b=fun(s2[j]);48             dp[0][j]=dp[0][j-1]+map[a][b];49         }50         for(i=1;i<=n;i++)51         {52             for(j=1;j<=m;j++)53             {54                 a=fun(s1[i]);55                 b=fun(s2[j]);56                 c=fun('-');57                 dp[i][j]=Max(dp[i-1][j]+map[a][c],dp[i][j-1]+map[c][b]);58                 dp[i][j]=Max(dp[i][j],dp[i-1][j-1]+map[a][b]);59             }60         }61         printf("%d\n",dp[n][m]);62     }63     return 0;64 }65