[CF1409F] Subsequences of Length Two

Description

给定一个长度为 (n le 200) 的字符串 (S)，和一个长度为 (2) 的字符串 (T)，可以在 (S) 中任意修改不超过 (m) 个字符得到 (S')，求 (S') 中与 (T) 相等的子序列的最大数量。

Solution

设 (T) 串为 ab，则定义 (f[i][j][k]) 表示对 (S') 中的前 (i) 位，其中有 (j) 个 a，且修改了 k 次的情况下，子序列的最大数量。转移时只需要枚举是否修改当前字符即可。

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

#define int long long
const int N = 205;

char s[N], t[N];
int f[N][N][N], n, m, ans;

void upd(int &x, int y)
{
    x = max(x, y);
}

signed main()
{
    ios::sync_with_stdio(false);

    cin >> n >> m >> s + 1 >> t + 1;
    char a = t[1], b = t[2];

    memset(f, -0x3f, sizeof f);
    f[0][0][0] = 0;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            for (int k = 0; k <= min(i, m); k++)
            {
                upd(f[i][j + (s[i] == a)][k], f[i - 1][j][k] + (s[i] == b) * j);
                upd(f[i][j + 1][k + 1], f[i - 1][j][k] + (a == b) * j);
                upd(f[i][j + (a == b)][k + 1], f[i - 1][j][k] + j);
            }
        }
    }

    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= n; j++)
            for (int k = 0; k <= m; k++)
                ans = max(ans, f[i][j][k]);

    cout << ans << endl;
}