Codeforces Round #683 (Div. 2, by Meet IT)D. Catching Cheaters

题意

给你两个字符串(A,B)，让你从(A，B)中找到连续的子串(C)，(D)其(4 * LCS(C,D) - |C| - |D|)最大，(LCS)是最长公共子序列

思路

最长公共子序列的变形，只需要求出每一步的贡献即可。

当(s1[i]==s2[j])时，贡献(+2)，但是需要注意负数的情况

当(s1[i]!=s2[j])时，贡献(-1)

#include<bits/stdc++.h>
 
using namespace std;
char s1[5005], s2[5005];
int dp[5005][5005];
void solve() {
    int n, m; cin >> n >> m;
    cin >> (s1 + 1) >> (s2 + 1);
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (s1[i] == s2[j]) {
                dp[i][j] = max(0, dp[i - 1][j - 1]) + 2;
            }else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) - 1;
            }
            ans = max(ans, dp[i][j]);
        }
    }
    cout << ans << endl;
}
 
signed main() {
    int t = 1;
    while (t--) {
        solve();
    }
}