此题与LCS非常相似。
因为是两个串的比对，所以我们很容易想到用f【i】【j】来表示a串的前i个碱基和b串的前j个碱基配出的最大相似度（每一个碱基都配对一个碱基，或者配空碱基），
那么这个状态的前驱就有三种：
①f【i】【j-1】+（b【j】与空碱基的相似度）
②f【i-1】【j】+（a【i】与空碱基的相似度）
③f【i-1】【j-1】+a【i】与b【j】的相似度
那么怎么表示相似度呢，用函数吗，当然是数组更方便
int mat[5][5]={{-1000,-3,-4,-2,-1},{-3,5,-1,-2,-1},{-4,-1,5,-3,-2},{-2,-2,-3,5,-2},{-1,-1,-2,-2,5}};（可以把读入的字符换成整数存起来）
完整代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=105;
int n,m;
char s1[N],s2[N],t;
int mat[5][5]={{-1000,-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 a[N],b[N],f[N][N];//0-0,1 2 3 4 1-0,1,2,3,4
void init();
int main()
{
//freopen("in.txt","r",stdin);
init();
memset(f,0x8f,sizeof(f));
f[0][0]=0;
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
{
int x1=mat[0][b[j]];
int x2=mat[a[i]][0];
int x3=mat[a[i]][b[j]];
/*if(i==2&&j==1){
cout<<f[i-1][j-1]<<" "<<a[i]<<" "<<b[j]<<endl;
}*/
if(i&&j) f[i][j]=max(f[i][j],f[i-1][j-1]+x3);
if(i) f[i][j]=max(f[i][j],f[i-1][j]+x2);
if(j) f[i][j]=max(f[i][j],f[i][j-1]+x1);
}
cout<<f[n][m]<<endl;
return 0;
}
void init()
{
cin>>n>>s1>>m>>s2;
for(int i=0;i<n;i++)
{
switch (s1[i])
{
case 'A':a[i+1]=1;break;
case 'C':a[i+1]=2;break;
case 'G':a[i+1]=3;break;
case 'T':a[i+1]=4;break;
default :break;
}
}
for(int i=0;i<m;i++)
{
switch (s2[i])
{
case 'A':b[i+1]=1;break;
case 'C':b[i+1]=2;break;
case 'G':b[i+1]=3;break;
case 'T':b[i+1]=4;break;
default :break;
}
}
}