题解：CF1409F Subsequences of Length Two

Forgetfulness · 2025-09-07 10:50:12 · 题解

Content

给你两个字符串 s 和 t，其中 1 \le |s| \le 200, |t| = 2。

最多可以修改 k 个 s 中的字符，问你修改完后 s 的子序列最多有多少个为 t。

Solution

首先我们注意到“子序列”，而 t 的长度只有 2，也就是说我们可以记从开头到当前位置出现过多少个 t_1，遇到 s_i = t_2 的情况就直接加上这个个数即可。

有了答案的快速贡献之后，我们考虑如何处理修改。

考虑记 dp_{i,j,l} 为从开头到第 i 个位置，共修改了 j 次，有 l 个 t_1（包括修改后的）。那么转移有这几种情况：

但我们发现当 s_i = t_i 时，t_1 也会有贡献，所以第二，三种真正的转移是需要加上 [t_1 = t_2] \times (l-1) 的，修改后的转移如下。

当然也有从后向前记 t_2 加 t_1 贡献的方法，只不过倒过来转而已。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 200 + 5;
int n, k;
string s, t;
long long dp[N][N][N];

int main () {

    ios::sync_with_stdio (0);
    cin.tie (0); cout.tie (0);

    cin >> n >> k;
    cin >> s >> t;
    s = " " + s, t = " " + t;

    // 因为比 max，初始化一个最小值。
    memset (dp, -0x7f, sizeof dp);
    dp[0][0][0] = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= k; ++j)
            for (int l = 0; l <= n; ++l) {
                if (s[i] != t[1] && s[i] != t[2]) dp[i][j][l] = dp[i - 1][j][l]; // 非 t 中元素
                // s_i = t_1 时
                if (s[i] != t[1] && j >= 1) dp[i][j][l] = max (dp[i][j][l], dp[i - 1][j - 1][l - 1] + (t[1] == t[2]) * (l - 1));
                else if (s[i] == t[1]) dp[i][j][l] = max (dp[i][j][l], dp[i - 1][j][l - 1] + (t[1] == t[2]) * (l - 1));
                // s_i = t_2 时
                if (s[i] != t[2] && j >= 1) dp[i][j][l] = max (dp[i][j][l], dp[i - 1][j - 1][l] + l);
                else if (s[i] == t[2]) dp[i][j][l] = max (dp[i][j][l], dp[i - 1][j][l] + l);
            }
    long long ans = 0;
    for (int i = 0; i <= k; ++i) for (int j = 0; j <= n; ++j) ans = max (ans, dp[n][i][j]);
    cout << ans;

    return 0;
}