DjvuLee

//@pku DY问题，最重要的是要找到最优子结构
//最优子结构为TAG标记处
//本题反映的就是子结构的最终边界返回出来不是很自然
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

#define N 120
#define MAX 10000//考虑到串最长不会超过100，全部匹配也只有500
int flag[N][N];

int dp(int pos1,int pos2);
int getVal(char ch1, char ch2);
int M[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,-10000}};
string s1,s2;
int main()
{
    int n;
    while(cin>>n){
        for(int i=0;i<n;i++)
        {
            int len1,len2;
            cin>>len1>>s1;
            cin>>len2>>s2;

            int cn=0;
            for(int i=0;i<N;i++)
                for(int j=0;j<N;j++)
                    flag[i][j]=MAX;
            cn=dp(s1.size()-1,s2.size()-1);
            cout<<cn<<endl;
        }
    }//end while
}


int dp(int pos1,int pos2)
{
    if(pos1==-1 && pos2 ==-1)
        return 0;
    if(pos1==-1)
    {
        return getVal('-',s2[pos2])+dp(-1,pos2-1);
    }
    if(pos2==-1)
    {
        return getVal(s1[pos1],'-')+dp(pos1-1,-1);
    }
    else
    {
        if(flag[pos1+1][pos2+1]!=MAX)
            return flag[pos1+1][pos2+1];
        else
        {
            int val1=getVal(s1[pos1],s2[pos2])+dp(pos1-1,pos2-1);
            int val2=getVal(s1[pos1],'-')+dp(pos1-1,pos2);
            int val3=getVal('-',s2[pos2])+dp(pos1,pos2-1);

            return flag[pos1+1][pos2+1]=max(val1,max(val2,val3));//TAG
        }
    }
}

int getVal(char ch1, char ch2)
{
    if(ch1==ch2)
        return 5;
    int pos1,pos2;
    switch(ch1){
        case 'A':{pos1=0;break;}
        case 'C':{pos1=1;break;}
        case 'G':{pos1=2;break;}
        case 'T':{pos1=3;break;}
        case '-':{pos1=4;break;}
    }//end switch
    switch(ch2){
        case 'A':{pos2=0;break;}
        case 'C':{pos2=1;break;}
        case 'G':{pos2=2;break;}
        case 'T':{pos2=3;break;}
        case '-':{pos2=4;break;}
    }//end switch
    
    return M[pos1][pos2];
}