The 2021 ICPC Asia Taipei Regional Programming Contest B Maximum Sub-Reverse Matching

题目描述

https://codeforces.com/gym/103443/problem/B

简要题意：给定两个长度为 $n$ 的串 $S$ 和 $T$，现在可以将 $T$ 的某一个子串翻转，求翻转后 $S$ 和 $T$ 最多有多少个对应位置相等

$n\le 1000$

Solution

对于这种区间翻转的问题，我们考虑区间 $dp$ 的思路，$f_{i,j}$ 由 $f_{i+1,j-1}$ 转移过来即可

#include <iostream>
#define maxn 1010
using namespace std;

int n;
char s[maxn], t[maxn];
int ans[maxn][maxn];

void work() {
    cin >> n >> s + 1 >> t + 1; int res = 0, mx = 0; 
    for (int i = 1; i <= n; ++i) res += s[i] == t[i];
    for (int len = 2; len <= n; ++len)
        for (int i = 1, j = len; j <= n; ++i, ++j) {
            ans[i][j] = ans[i + 1][j - 1] - (s[i] == t[i]) - (s[j] == t[j]) + (s[i] == t[j]) + (s[j] == t[i]);
            mx = max(mx, ans[i][j]);
        }
    for (int len = 1; len <= n; ++len)
        for (int i = 1, j = len; j <= n; ++i, ++j)
            if (ans[i][j] == mx) return cout << res << " " << res + mx << " " << i << " " << j << "\n", void();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) work(); 
    return 0;
}