CodeForces - Problem 1447 - Catching Cheaters - DP

#include <bits/stdc++.h>
using namespace std;
const int N = 5000+5;
char a[N],b[N];
int dp[N][N]; 
// Let DP[i][j] be the maximum similarity score if we end the first substring with Ai and the second substring with Bj.
int main(){
    int ans=0;
    int n,m;
    scanf("%d%d",&n,&m);
    scanf("%s%s",a+1,b+1);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i]==b[j]){
                dp[i][j]=max(2,dp[i-1][j-1]+2); // 2 represent only a[i] and b[j]
            }else{
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])-1;
            }
            ans=max(ans,dp[i][j]);
        }
    } 

    printf("%d",ans);
    system("pause");
    return 0;
}

CodeForces - Problem 1447 - Catching Cheaters - DP

原文：https://www.cnblogs.com/popodynasty/p/13993556.html