动态规划，关键是准确地找出转移方程和边界条件
转移方程 m[i][j]= max{ m[i-1][j-1]+a[s1[i]][s2[j]] , m[i-1][j]+a[s1[i]][4] , m[i][j-1]+a[4][s2[j]] }
边界 m[i][0]=m[i-1][0]+a[s1[i]][4]；
m[0][j]=m[0][j-1]+a[4][s2[j]]；
#include <iostream>
using namespace std;
int main()
{
int T,z;
int i,j;
cin>>T;
int a[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,-2000};
int s1[101],s2[101];
char str1[101],str2[101];
for(z=0;z<T;z++)
{
int m[101][101]={{0}};
cin>>s1[0];
cin>>str1;
for(i=0;i<s1[0];i++)
{
switch(str1[i])
{
case 'A': s1[i+1]=0; break;
case 'C': s1[i+1]=1; break;
case 'G': s1[i+1]=2; break;
case 'T': s1[i+1]=3; break;
}
}
cin>>s2[0];
cin>>str2;
for(i=0;i<s2[0];i++)
{
switch(str2[i])
{
case 'A': s2[i+1]=0; break;
case 'C': s2[i+1]=1; break;
case 'G': s2[i+1]=2; break;
case 'T': s2[i+1]=3; break;
}
}
for(i=1;i<=s1[0];i++)
m[i][0]=m[i-1][0]+a[s1[i]][4];
for(j=1;j<=s2[0];j++)
m[0][j]=m[0][j-1]+a[4][s2[j]];
for(i=1;i<=s1[0];i++)
for(j=1;j<=s2[0];j++)
{
int max=m[i-1][j-1]+a[s1[i]][s2[j]];
if(m[i-1][j]+a[s1[i]][4]>max) max=m[i-1][j]+a[s1[i]][4];
if(m[i][j-1]+a[4][s2[j]]>max) max=m[i][j-1]+a[4][s2[j]];
m[i][j]=max;
}
cout<<m[s1[0]][s2[0]]<<endl;
}
return 0;
}