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();
    }
}

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

原文：https://www.cnblogs.com/waryan/p/13984519.html