Lisa

显然两个在一起的空格是没有意义的。

所以空格的相对的一定是字符

这样在匹配的时候考虑对于两个字符，加不加空格和加在哪里

因为连续的空格有额外贡献

所以要记录有没有和在哪里

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
using namespace std;
int f[3005][3005][5];
int p[5][5];
char s1[3005],s2[3005]; 
map<char,int> ma;
int l1,l2;
int a,b;
int main(){
    ma['A']=1;
    ma['T']=2;
    ma['G']=3;
    ma['C']=4;
    scanf("%s",s1+1);
    scanf("%s",s2+1);
    l1=strlen(s1+1);
    l2=strlen(s2+1);
    for(int i=1;i<=4;++i){
        for(int j=1;j<=4;++j){
            scanf("%d",&p[i][j]);
        }
    }
    scanf("%d%d",&a,&b);
    memset(f,0xc0,sizeof(f));
    f[0][0][0]=0;
    for(int i=0;i<=l1;++i){
        for(int j=0;j<=l2;++j){
            if(i+j==0) continue;
            if(i!=0&&j!=0) f[i][j][0]=max(max(f[i-1][j-1][0],f[i-1][j-1][1]),f[i-1][j-1][2])+p[ma[s1[i]]][ma[s2[j]]];
            if(j!=0) f[i][j][1]=max(max(f[i][j-1][0]-a,f[i][j-1][1]-b),f[i][j-1][2]-a);
            if(i!=0) f[i][j][2]=max(max(f[i-1][j][0]-a,f[i-1][j][1]-a),f[i-1][j][2]-b);
        }
    }
    cout<<max(max(f[l1][l2][0],f[l1][l2][1]),f[l1][l2][2]);
    return 0;
}