CF 1447D Catching Cheaters

题目描述

https://codeforces.com/contest/1447/problem/D

Solution

注意到这东西跟 $LCS$ 的要求的东西非常像，我们发现唯一的不同就是需要减掉串的长度

那么我们可以用类似的方法维护 $dp$ 数组

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cctype>
#define maxn 5010
#define ll long long
#define cn const node
#define gc getchar
#define pb push_back
using namespace std;

ll read() {
    ll x = 0, f = 0; char c = gc();
    while (!isdigit(c)) f |= c == '-', c = gc();
    while (isdigit(c)) x = x * 10 + c - '0', c = gc();
    return f ? -x : x;
}

inline int max(int a, int b, int c) { return max(a, max(b, c)); } 

int n, m;

char s[maxn], t[maxn];

int f[maxn][maxn], ans;
int main() {
    scanf("%d%d%s%s", &n, &m, s + 1, t + 1);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) { 
            if (s[i] == t[j]) 
                f[i][j] = max(f[i][j], f[i - 1][j - 1] + 2);
            else f[i][j] = max(f[i - 1][j] - 1, f[i][j - 1] - 1, 0); // 因为是子串，所以可以随时从 0 开始
            ans = max(ans, f[i][j]);
        }
    cout << ans << endl; 
    return 0;
}