题目：https://www.luogu.org/problemnew/show/P4059
DP，状态应分为空格或字母，可用0和1表示，据此转移，详见代码。
另：注意初始化，因为有负值所以要先把f数组赋一个很小的值，再据题意赋值与0有关的f，特别的，f[0][0][1][1]=0。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int d[5][5],A,B,a[3005],b[3005],n,m,f[3005][3005][3][3],ans;
char dc[3005];
int main()
{
// freopen("dna.in","r",stdin);
// freopen("dna.out","w",stdout);
gets(dc);
n=strlen(dc);
for(int i=1;i<=n;i++)
{
if(dc[i-1]=='A')a[i]=1;
if(dc[i-1]=='T')a[i]=2;
if(dc[i-1]=='G')a[i]=3;
if(dc[i-1]=='C')a[i]=4;
}
gets(dc);
m=strlen(dc);
for(int i=1;i<=m;i++)
{
if(dc[i-1]=='A')b[i]=1;
if(dc[i-1]=='T')b[i]=2;
if(dc[i-1]=='G')b[i]=3;
if(dc[i-1]=='C')b[i]=4;
}
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++)
scanf("%d",&d[i][j]);
scanf("%d%d",&A,&B);
memset(f,-3,sizeof f);//!
// f[0][0][1][0]=f[0][0][0][1]=f[0][0][1][1]=0;//!!
f[0][0][1][1]=0;
f[1][0][1][0]=-A;
for(int i=2;i<=n;i++)
f[i][0][1][0]=f[i-1][0][1][0]-B;
f[0][1][0][1]=-A;
for(int i=2;i<=m;i++)
f[0][i][0][1]=f[0][i-1][0][1]-B;
// scanf("%d%d",&A,&B);//!!!顺序!!!
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
// f[i][j][0][1]=max(f[i][j][0][1],f[i][j-1][1][1]-A);
// f[i][j][0][1]=max(f[i][j][0][1],f[i][j-1][0][1]-B);
// f[i][j][0][1]=max(f[i][j][0][1],f[i][j-1][1][0]-A);
f[i][j][0][1]=max(f[i][j-1][0][1]-B,max(f[i][j-1][1][1],f[i][j-1][1][0])-A);
// f[i][j][1][1]=max(f[i][j][1][1],f[i-1][j-1][1][1]+d[a[i]][b[j]]);
// f[i][j][1][1]=max(f[i][j][1][1],f[i-1][j-1][0][1]+d[a[i]][b[j]]);
// f[i][j][1][1]=max(f[i][j][1][1],f[i-1][j-1][1][0]+d[a[i]][b[j]]);
f[i][j][1][1]=max(f[i-1][j-1][1][1],max(f[i-1][j-1][0][1],f[i-1][j-1][1][0]))+d[a[i]][b[j]];
// f[i][j][1][0]=max(f[i][j][1][0],f[i-1][j][1][1]-A);
// f[i][j][1][0]=max(f[i][j][1][0],f[i-1][j][0][1]-A);
// f[i][j][1][0]=max(f[i][j][1][0],f[i-1][j][1][0]-B);
f[i][j][1][0]=max(f[i-1][j][1][0]-B,max(f[i-1][j][1][1],f[i-1][j][0][1])-A);
}
ans=max(f[n][m][1][1],max(f[n][m][0][1],f[n][m][1][0]));
printf("%d",ans);
return 0;
}