题解 CF1446B 【Catching Cheaters】

Piwry · 2020-11-17 20:06:05 · 题解

解析

直接魔改下 O(n^2) 最长公共子序列的 dp 式子即可

具体来说，设 dp(i, j) 表示 C 为 0..A_{i-1} 后缀，D 为 0..B_{j-1} 后缀，的最大贡献

转移时也和公共子序列一样，考虑匹配 i, j 或不匹配 i, j 的情况即可。但要注意更长的子串（C, D）不一定能获得更大的贡献，因此还要考虑一种仅选择 i, j 这两处的情况（由于上面的 dp 状态定义，这不能从 dp(i-1, j-1) 或 dp(i-1, j) 或 dp(i, j-1) 转移得到）

还有不理解的地方可参考代码

CODE

#include <cstdio>
#include <iostream>
using std::max;

const int MAXN =5050;

int dp[MAXN][MAXN];/*C 为 0..A_{i-1} 后缀，D 为 0..B_{j-1} 后缀，的最大贡献*/

char s1[MAXN], s2[MAXN];

int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    scanf("%s%s", s1, s2);
    int ans =0;/*初值注意下 C, D 均空也是一种答案*/
    for(int i =1; i <= n; ++i)
        dp[i][0] =-i;
    for(int j =1; j <= m; ++j)
        dp[0][j] =-j;
    for(int i =1; i <= n; ++i)
        for(int j =1; j <= m; ++j){
            if(s1[i-1] == s2[j-1]){/*尝试匹配 i, j*/
                int tmp1 =dp[i-1][j-1]+4*1-2,
                    tmp2 =4*1-2;
                dp[i][j] =max(tmp1, tmp2);

            }
            else{
                int tmp1 =dp[i-1][j-1]-2,
                    tmp2 =-2;
                dp[i][j] =max(tmp1, tmp2);
            }
            int tmp01 =dp[i-1][j]-1,/*不尝试匹配 i, j*/
                tmp02 =dp[i][j-1]-1;
            dp[i][j] =max(dp[i][j], max(tmp01, tmp02));
            ans =max(ans, dp[i][j]);
        }
    printf("%d", ans);
}