hdu1080

#include<iostream> using namespace std; char s1[105],s2[105]; int val[5][5]={ {5,-1,-2,-1,-3}, {-1,5,-3,-2,-4}, {-2,-3,5,-2,-2}, {-1,-2,-2,5,-1}, {-3,-4,-2,-1,-1000000}}; int dp[105][105]; //dp[i][j]表示字符串i和j的最长公共子序列 int n,m; int max(int a,int b) { return a>b?a:b; } int id(char c) { switch(c) { case 'A': return 0; break; case 'C': return 1; break; case 'G': return 2; break; case 'T': return 3; break; } } int fun() { int i,j; memset(dp,0,sizeof(dp)); for(i=1;i<=n;i++) dp[i][0]=dp[i-1][0]+val[id(s1[i-1])][4]; for(j=1;j<=m;j++) dp[0][j]=dp[0][j-1]+val[id(s2[j-1])][4]; for(i=1;i<=n;i++) for(j=1;j<=m;j++) dp[i][j]=max(dp[i-1][j]+val[id(s1[i-1])][4], max(dp[i][j-1]+val[id(s2[j-1])][4],dp[i-1][j-1]+val[id(s1[i-1])][id(s2[j-1])])); return dp[n][m]; } int main() { int T; cin>>T; while(T--) { cin>>n>>s1>>m>>s2; cout<<fun()<<endl; } return 0; }