学步园

/*This Code is Submitted by Iris for Problem 1316 at 2013-07-26 12:19:13*/
#include <iostream>
#include <algorithm>
using namespace std;
//这个问题用DP的话,需要考虑
//dp[i][j]表示长为i,j时的最大相似度
//dp[i][j] = max{dp[i-1][j-1]+cal[i][j],
//               dp[i][j-1]+cal['-'][j],
//               dp[i-1][j]+cal[i]['-']}.
/**通过分析非常小规模的问题可以看出来,
这种转移方程可以表示出插入空格的情况**/
/**目前只能说,通过猜想状态转移方程(套模板)并且分析小规模问题
观察方程运转情况来证明其正确性,对其正确性的证明还没有更深的理解**/
int a[110],b[110],v[110][110];
int r[5][5]={{0,-3,-4,-2,-1},
             {-3,5,-1,-2,-1},
             {-4,-1,5,-3,-2},
             {-2,-2,-3,5,-2},
             {-1,-1,-2,-2,5}};
int change(char c){
    switch (c){
    case'A': return 1;
    case'C': return 2;
    case'G': return 3;
    case'T': return 4;
    default: return 0;
    }
}
int main(){
    int n,st1len,st2len,i,j;
    char ch;
    cin>>n;
    while(n--)
    {
        cin>>st1len;
        for(i=1;i<=st1len;i++){
            cin>>ch;//cin will ignore leading blanks
            a[i]=change(ch);
        }
        cin>>st2len;
        for(i=1;i<=st2len;i++){
            cin>>ch;
            b[i]=change(ch);
        }
        v[0][0]=0;
        for(i=1;i<=st1len;i++) v[i][0]=r[a[i]][0]+v[i-1][0];//str1 全部和blank匹配的结果
        for(i=1;i<=st2len;i++) v[0][i]=r[0][b[i]]+v[0][i-1];//str2 全部和blank匹配的结果
        for(i=1;i<=st1len;i++)
            for(j=1;j<=st2len;j++)
                v[i][j]=max(v[i-1][j-1]+r[a[i]][b[j]],
                max(v[i-1][j]+r[a[i]][0],v[i][j-1]+r[0][b[j]]));
            cout<<v[st1len][st2len]<<endl;
    }
    return 0;
}