题目大意：

太长的英语，我就直接读了测试样例和题目中一些可以看的。。。。好像是关于什么人类基因工程什么的，
腺嘌呤脱氧核糖核苷酸~
每组测试实例给你两串由AGCT四个字母组成的字符串（每个字符串100字符）。
有一个得分表：

分析：

说出来你们可能不相信，这个题我还没想很明白就应开始写了，然后居然写出来了。当时就是还没怎么仔细想好细节，就想，我要知道这个，就只要知道另外的几个其他的状态就好了，并没有很清楚的想明白初始条件，以及这么递归下去会递归到什么样子。

dp建立：

dp [ i ] [ j ]表示第一行前 i 个字符和第二行前 j 个字符进行匹配最多可以获得多少的得分。
递推方程：
dp [ i ] [ j ]=max { dp [ x-1 ] [ y ] + move [ a[x] ] [ 5 ] , dp [ x ] [ y-1 ] + move [ 5 ] [ b[y] ] , dp [ x-1 ] [ y-1 ] + move [ a[x] ] [ b[y] ] }

这次用的是递归，不是递推。然后为了防止重复计算，使用 best [ ] [ ] 数组记录每次递归下来的结果。类似于记忆化搜索吧。

#include<iostream>
#include<string.h>
#include<stdio.h>
#define inf 0x3f3f3f3f
using namespace std;

int n;
//int dp[150][150]={0};
int a[150]={0};
int b[150]={0};
int move[6][6]={0,0,0,0,0,0,0,5,-1,-2,-1,-3,0,-1,5,-3,-2,-4,0,-2,-3,5,-2,-2,0,-1,-2,-2,5,-1,0,-3,-4,-2,-1,-inf};
int best[150][150]={0};

void input()
{
    cin>>a[0];
    getchar();
    for(int i=1;i<=a[0];i++)
    {
        char l;
        scanf("%c",&l);
        if(l=='A')a[i]=1;
        if(l=='C')a[i]=2;
        if(l=='G')a[i]=3;
        if(l=='T')a[i]=4;
    }
    cin>>b[0];
    getchar();
    for(int i=1;i<=b[0];i++)
    {
        char l;
        scanf("%c",&l);
        if(l=='A')b[i]=1;
        if(l=='C')b[i]=2;
        if(l=='G')b[i]=3;
        if(l=='T')b[i]=4;
    }
}

int my_max(int aa,int bb,int cc)
{
    int t=aa;
    if(t<bb)t=bb;
    if(t<cc)t=cc;
    return t;
}
int dp(int x,int y)
{
    if(x==0&&y==0)return 0;
    if(best[x][y]!=0)return best[x][y];
    /*if(a[x]==b[y]) { best[x][y]=dp(x-1,y-1)+5; return best[x][y]; }*/
    best[x][y]=my_max(dp(x-1,y)+move[a[x]][5],dp(x,y-1)+move[5][b[y]],dp(x-1,y-1)+move[a[x]][b[y]]);
    return best[x][y];

}

void init()
{
    for(int i=1;i<=a[0];i++)
    {
        best[i][0]=best[i-1][0]+move[a[i]][5];
    }
    for(int i=1;i<=b[0];i++)
    {
        best[0][i]=best[0][i-1]+move[5][b[i]];
    }
}

int main()
{
    int test;
    cin>>test;
    while(test--)
    {
        input();
        //cout<<a[0]<<b[0];
        init();
        cout<<dp(a[0],b[0])<<endl;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(best,0,sizeof(best));
    }
}