题解 CF1446B 【Catching Cheaters】

· · 题解

Codeforces 1446B

Solution

令 f(i,j) 表示 A 的前 i 位，B 的前 j 位能够得到的最大分数，则容易得到转移方程：

f(i,j)=\begin{cases}\max\{f(i,j-1),f(i-1,j)\}-1, &A_i\not=B_j\\ f(i-1,j-1)+2, &A_i=B_j\end{cases}

注意过程中分数有可能是负数，随时和 0 取 \max 即可。

Code

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=5000;
int dp[N+10][N+10];
char s1[N+10],s2[N+10];
int main()
{
    int n,m,ans=0;
    scanf("%d%d%s%s",&n,&m,s1+1,s2+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            dp[i][j]=max(0,max(dp[i][j-1],dp[i-1][j])-1);
            if(s1[i]==s2[j]) dp[i][j]=max(dp[i][j],dp[i-1][j-1]+2);
            ans=max(ans,dp[i][j]);
        }
    printf("%d",ans);
}