#include<bits/stdc++.h>
using namespace std;
#define int long long
map<char,int>x;
char a[105],b[105];
int f[105][105],lena,lenb,sum[2][105];
bool p;
int q[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,0}
};
signed main(){
//freopen("1.in","r",stdin);
for(int i=0;i<=104;i++)
for(int j=0;j<=104;j++)
f[i][j]=-1e9;
f[0][0]=0;
x['A']=0;
x['C']=1;
x['G']=2;
x['T']=3;
x['-']=4;
scanf("%lld %s\n",&lena,a);
scanf("%lld %s",&lenb,b);
for(int i=lena;i>=1;i--) a[i]=a[i-1];
for(int i=lenb;i>=1;i--) b[i]=b[i-1];
for(int i=1;i<=lena;i++) sum[0][i]=sum[0][i-1]+q[4][x[a[i]]],f[i][0]=sum[0][i]; //赋初值
for(int i=1;i<=lenb;i++) sum[1][i]=sum[1][i-1]+q[4][x[b[i]]],f[0][i]=sum[1][i]; //赋初值
//以上为求连续 - + 字母 的前缀相似度,
for(int i=1;i<=lena;i++){
for(int j=1;j<=lenb;j++){
int t,r,u;
char a_,b_;//都是过程变量
if(i>j) p=0,t=j,r=i;
else p=1,t=i,r=j;
for(int k=t;k<=r;k++){//枚举最后一个较短串字符对应哪一个较长串字符
if(p) u=f[t-1][k-1],a_=a[t],b_=b[k];
else u=f[k-1][t-1],a_=a[k],b_=b[t];
f[i][j]=max(f[i][j],u+q[x[a_]][x[b_]]+sum[p][r]-sum[p][k]);//DP
}
}
}
//for(int i=1;i<=lena;i++){
// for(int j=1;j<=lenb;j++){
// cout<<i<<" "<<j<<":"<<f[i][j]<<endl;
// }
//}
cout<<f[lena][lenb];
return 0;
}
到底是状态转移方程的问题呢还是实现的问题,请求解答。