//Accepted 200 KB 0 ms //dp //dp[i][j]表示s1用前i个,s2用前j个字符能得到的最大分数 //dp[i][j]=max(dp[i-1][j]+score[s1[i-1]]['-'], // dp[i][j-1]+score[['-'][s2[j-1]], // dp[i-1][j-1]+score[s1[i-1]][s2[j-1]]) //注意初始化 //dp[0][0]=0; //dp[0][i]=dp[0][i-1]+score['-'][s2[i-1]] //dp[i][0]=dp[i-1][0]+score[s1[i-1]]['-'] //还要初始化dp[i][j]=-inf; #include <cstdio> #include <cstring> #include <iostream> using namespace std; ; ; int dp[imax_n][imax_n]; int n1,n2; char s1[imax_n]; char s2[imax_n]; int getScore(char ch1,char ch2) { ; ; ; ; ; if (ch1=='C') { ; ; ; ; } if (ch1=='G') { ; ; ; ; } if (ch1=='T') { ; ; ; ; } if (ch1=='-') { ; ; ; ; } } void Dp() { //memset(dp,0,sizeof(dp)); dp[][]=; ;i<=n1;i++) dp[i][]=dp[i-][]+getScore(s1[i-],'-'); ;i<=n2;i++) dp[][i]=dp[][i-]+getScore(]); ;i<=n1;i++) { ;j<=n2;j++) { dp[i][j]=inf; ]+getScore(])>dp[i][j]) dp[i][j]=dp[i][j-]+getScore(]); ][j]+getScore(s1[i-],'-')) dp[i][j]=dp[i-][j]+getScore(s1[i-],'-'); ][j-]+getScore(s1[i-],s2[j-])) dp[i][j]=dp[i-][j-]+getScore(s1[i-],s2[j-]); } } printf("%d\n",dp[n1][n2]); } int main() { int T; scanf("%d",&T); while (T--) { scanf("%d",&n1); scanf("%s",s1); scanf("%d",&n2); scanf("%s",s2); Dp(); } ; }