1 //Accepted    200 KB    0 ms 2 //dp 3 //dp[i][j]表示s1用前i个,s2用前j个字符能得到的最大分数 4 //dp[i][j]=max(dp[i-1][j]+score[s1[i-1]][‘-‘], 5 //             dp[i][j-1]+score[[‘-‘][s2[j-1]], 6 //             dp[i-1][j-1]+score[s1[i-1]][s2[j-1]]) 7 //注意初始化 8 //dp[0][0]=0; 9 //dp[0][i]=dp[0][i-1]+score[‘-‘][s2[i-1]]10 //dp[i][0]=dp[i-1][0]+score[s1[i-1]][‘-‘]11 //还要初始化dp[i][j]=-inf;12 #include <cstdio>13 #include <cstring>14 #include <iostream>15 using namespace std;16 const int imax_n = 105;17 const int inf = -1000000;18 int dp[imax_n][imax_n];19 int n1,n2;20 char s1[imax_n];21 char s2[imax_n];22 int getScore(char ch1,char ch2)23 {24     if (ch1==ch2) return 5;25     if (ch1==‘A‘ && ch2==‘C‘) return -1;26     if (ch1==‘A‘ && ch2==‘G‘) return -2;27     if (ch1==‘A‘ && ch2==‘T‘) return -1;28     if (ch1==‘A‘ && ch2==‘-‘) return -3;29     if (ch1==‘C‘)30     {31         if (ch2==‘A‘) return -1;32         if (ch2==‘G‘) return -3;33         if (ch2==‘T‘) return -2;34         if (ch2==‘-‘) return -4;35     }36     if (ch1==‘G‘)37     {38         if (ch2==‘A‘) return -2;39         if (ch2==‘C‘) return -3;40         if (ch2==‘T‘) return -2;41         if (ch2==‘-‘) return -2;42     }43     if (ch1==‘T‘)44     {45         if (ch2==‘A‘) return -1;46         if (ch2==‘C‘) return -2;47         if (ch2==‘G‘) return -2;48         if (ch2==‘-‘) return -1;49     }50     if (ch1==‘-‘)51     {52         if (ch2==‘A‘) return -3;53         if (ch2==‘C‘) return -4;54         if (ch2==‘G‘) return -2;55         if (ch2==‘T‘) return -1;56     }57 }58 void Dp()59 {60     //memset(dp,0,sizeof(dp));61     dp[0][0]=0;62     for (int i=1;i<=n1;i++)63     dp[i][0]=dp[i-1][0]+getScore(s1[i-1],‘-‘);64     for (int i=1;i<=n2;i++)65     dp[0][i]=dp[0][i-1]+getScore(‘-‘,s2[i-1]);66     for (int i=1;i<=n1;i++)67     {68         for (int j=1;j<=n2;j++)69         {70             dp[i][j]=inf;71             if (dp[i][j-1]+getScore(‘-‘,s2[j-1])>dp[i][j])72             dp[i][j]=dp[i][j-1]+getScore(‘-‘,s2[j-1]);73             if (dp[i][j]<dp[i-1][j]+getScore(s1[i-1],‘-‘))74             dp[i][j]=dp[i-1][j]+getScore(s1[i-1],‘-‘);75             if (dp[i][j]<dp[i-1][j-1]+getScore(s1[i-1],s2[j-1]))76             dp[i][j]=dp[i-1][j-1]+getScore(s1[i-1],s2[j-1]);77         }78     }79     printf("%d\n",dp[n1][n2]);80 }81 int main()82 {83     int T;84     scanf("%d",&T);85     while (T--)86     {87         scanf("%d",&n1);88         scanf("%s",s1);89         scanf("%d",&n2);90         scanf("%s",s2);91         Dp();92     }93     return 0;94 }