题目直达车

#include<bits/stdc++.h>
using namespace std;
#define maxn 3010

int l1,l2,A,B;
string s1,s2;
int dp[maxn][maxn][2][2];
//dp[i][j][0/1][0/1]表示DNA1第i个下标起，DNA2第j个下标起，相似度最大值（0/1表示前面是否有空格）

int d[4][4];
int get(char a){
    if(a=='A')return 0;
    else if(a=='T')return 1;
    else if(a=='G')return 2;
    else if(a=='C')return 3;
}

int main(){
    memset(dp,-0x3f,sizeof(dp));
    cin>>s1>>s2;
    l1=s1.size(),l2=s2.size();
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++)cin>>d[i][j];
    }
    cin>>A>>B;
    dp[l1][l2][0][0]=dp[l1][l2][1][0]=dp[l1][l2][0][1]=0;//刚好匹配完：不加相似度
    for(int i=l1;i>=0;i--){//倒着dp
        for(int j=l2;j>=0;j--){
            if(i==l1&&j!=l2){
                dp[i][j][0][0]=dp[i][j][1][0]=dp[i][j][0][1]=-A-B*(l2-j-1);//一串匹配完，另一串只能全配空格
            }else if(i!=l1&&j==l2){
                dp[i][j][0][0]=dp[i][j][1][0]=dp[i][j][0][1]=-A-B*(l1-i-1);//同理
            }else if(i!=l1&&j!=l2){
                dp[i][j][0][0]=max(dp[i+1][j+1][0][0]+d[get(s1[i])][get(s2[j])],max(dp[i+1][j][1][0],dp[i][j+1][0][1])-A);//如果都没有空格：1.匹配两段 2.DNA1匹配空格 3.DNA2匹配空格
                dp[i][j][1][0]=max(dp[i+1][j+1][0][0]+d[get(s1[i])][get(s2[j])],dp[i+1][j][1][0]-B);
                //DNA1有空格：1.匹配两段 2.继续加空格
                dp[i][j][0][1]=max(dp[i+1][j+1][0][0]+d[get(s1[i])][get(s2[j])],dp[i][j+1][0][1]-B);
                //DNA2有空格：1.匹配两段 2.继续加空格
            }
        }
    }
    cout<<max(dp[0][0][0][0],max(dp[0][0][1][0],dp[0][0][0][1]));
    
    return 0;
}