题目大意：两串基因进行匹配（可能不一样长，不够就添加空格），任何两碱基之间以及碱基和空格匹配时所得分数已给出，求可以达到的最大分值。
动态规划，两串基因存放在a，b数组中，用ans[ i ][ j ]表示a中前 i 个碱基和b中前 j 个碱基配对时的最大分数，则状态转移方程可以写为： ans[i][j]=max( ans[ i-1 ][ j-1 ] + w[ a[i] ][ b[j] ], ans[ i ][ j-1 ] + w[ 5 ][ b[j] ], ans[ i-1 ][ j ]+ w[ a[i] ][ 5 ] )，w数组存放碱基配对时的分数其中空格在第五列和第五行，该方程的意思为：对于a中前 i 个碱基和b中前 j 个碱基配对时情况有三种，分别为是a[ i ]和b[ j ]配对，
a[ i ]和空格配对，b[ j ]和空格配对，满足最优子结构。
#include <stdio.h>
#include <string.h>
#define INF 10000
int w[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 max(int a,int b,int c)
{
int x=-INF;
if(a>x) x=a;
if(b>x) x=b;
if(c>x) x=c;
return x;
}
int main()
{
int t;
char c;
int i,j,l1,l2;
int a[110],b[110]; //存放两个基因串
int ans[110][110]; //ans[i][j]
scanf("%d",&t);
while(t--)
{
memset(ans,0,sizeof(ans));
scanf("%d",&l1);
getchar();
for(i=1;i<=l1;i++)
{
scanf("%c",&c);
if(c=='A')
a[i]=1;
else if(c=='C')
a[i]=2;
else if(c=='G')
a[i]=3;
else
a[i]=4;
}
scanf("%d",&l2);
getchar();
for(i=1;i<=l2;i++)
{
scanf("%c",&c);
if(c=='A')
b[i]=1;
else if(c=='C')
b[i]=2;
else if(c=='G')
b[i]=3;
else
b[i]=4;
}
for(i=1;i<=l1;i++)
ans[i][0]=ans[i-1][0]+w[a[i]][5]; //初始化
for(i=1;i<=l2;i++)
ans[0][i]=ans[0][i-1]+w[5][b[i]];
for(i=1;i<=l1;i++)
for(j=1;j<=l2;j++)
ans[i][j]=max(ans[i-1][j-1]+w[a[i]][b[j]],ans[i][j-1]+w[5][b[j]],ans[i-1][j]+w[a[i]][5]);
printf("%d
",ans[l1][l2]);
}
return 0;
}