CF1409F「Subsequences of Length Two」

1. 题目

题目链接：CF1409F「Subsequences of Length Two」。

Description

You are given two strings $s$ and $t$ consisting of lowercase Latin letters. The length of $t$ is $2$ ( $i.e.$ this string consists only of two characters).

In one move, you can choose any character of s and replace it with any lowercase Latin letter. More formally, you choose some $i$ and replace $s_i$ (the character at the position $i$ ) with some character from 'a' to 'z'.

You want to do no more than $k$ replacements in such a way that maximizes the number of occurrences of $t$ in $s$ as a subsequence.

Recall that a subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.

Input

The first line of the input contains two integers $n$ and $k$ ( $2 \leq n \leq 200; 0 \leq k \leq n$ ) — the length of $s$ and the maximum number of moves you can make. The second line of the input contains the string $s$ consisting of $n$ lowercase Latin letters. The third line of the input contains the string $t$ consisting of two lowercase Latin letters.

Output

Print one integer — the maximum possible number of occurrences of t in $s$ as a subsequence if you replace no more than $k$ characters in $s$ optimally.

Examples

input #1

1
2
3

4 2
bbaa
ab

output #1

input #2

1
2
3

7 3
asddsaf
sd

output #2

input #3

1
2
3

15 6
qwertyhgfdsazxc
qa

output #3

input #4

1
2
3

7 2
abacaba
aa

output #4

2. 题解

分析

一般这种最优计数问题应该想到使用 $dp$ ，但是 $dp$ 最困难的在于构造状态以及状态转移方程。对于这道题的 $dp$ 构造，蒟蒻的我毫无头绪，只好看比赛题解（Orz）。

首先定义状态： $dp(i,j,u)$ 表示处理完字符串 $s$ 的第 $i$ 个字符后，已经使用了 $j$ 个 $move$ 操作，且字符串 $s[0..i-1]$ 中有 $u$ 个字符 $t[0]$ ，此时字符串 $s[0..i-1]$ 中包含的子序列 $t$ 的最大个数。
然后构造状态转移方程：设 $e_0 = 1$ 表示 $s[i] = t[0]$ ，否则 $e_0 = 0$ ；设 $e_1 = 1$ 表示 $s[i] = t[1]$ ，否则 $e_1 = 0$ ；设 $e_{01} = 1$ 表示 $t[0] = t[1]$ ，否则 $e_{01} = 0$ 。

如果不处理第 $i$ 个字符，则有：

$\begin{array}{c} dp[i+1][j][u+e_0] = max(dp[i+1][j][u+e_0], dp[i][j][u]+(e_1?u:0)) \end{array}$

如果将第 $i$ 个字符替换为 $t[0]$ ，则有：

$\begin{array}{c} dp[i+1][j+1][u+1] = max(dp[i+1][j+1][u+1], dp[i][j][u]+(e_{01}?u:0)) \end{array}$

如果将第 $i$ 个字符替换为 $t[1]$ ，则有：

$\begin{array}{c} dp[i+1][j+1][u+e_{01}] = max(dp[i+1][j+1][u+e_{01}], dp[i][j][u]+u) \end{array}$

构造出了转移方程后，最重要的是确定边界。首先易知的是对于第 2 和 3 个方程，要求 $j \lt k$ ；然后是初始条件 $dp[0][0][0] = 0$ 。然而似乎 $u$ 的边界不好确定，我们需要保证处理的都是可能出现的情况，所以需要将不可能的情况筛去，观察到每个转移方程的最优解都取决于子问题的最优解 $dp[i][j][u]$ ，因此，我们可以初始化数组 $dp$ 所有元素值为 -1，然后根据初始条件 $dp[0][0][0] = 0$ ，往后拓展，在进行状态转移时，如果遇到 $dp[i][j][u] = -1$ 的情况时，就直接跳过，因为这说明这种情况不能由初始情况 $dp[0][0][0] = 0$ 推导而来。

代码

#include <bits/stdc++.h>
#define ll int
#define MAXN 205
using namespace std;

ll dp[MAXN][MAXN][MAXN];

ll answer(char *str, ll n, char *ptr, ll k) {
    ll e01 = ptr[0] == ptr[1];
    memset(dp, -1, sizeof(dp));
    dp[0][0][0] = 0;
    for(ll i = 0; i < n; ++i) {
        ll e0 = str[i] == ptr[0];
        ll e1 = str[i] == ptr[1];
        for(ll j = 0; j <= k; ++j) {
            for(ll t = 0; t <= n; ++t) {
                if(dp[i][j][t] == -1)   continue;
                dp[i+1][j][t+e0] = max(dp[i+1][j][t+e0], dp[i][j][t]+(e1?t:0));
                if(j < k) {
                    dp[i+1][j+1][t+1] = max(dp[i+1][j+1][t+1], dp[i][j][t]+(e01?t:0));
                    dp[i+1][j+1][t+e01] = max(dp[i+1][j+1][t+e01], dp[i][j][t]+t);
                }
            }
        }
    }
    ll ans = 0;
    for(ll j = 0; j <= k; ++j) {
        for(ll t = 0; t <= n; ++t) {
            ans = max(ans, dp[n][j][t]);
        }
    }
    return ans;
}

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    char str[205], ptr[4];
    scanf("%s%s", str, ptr);
    int ans = answer(str, n, ptr, k);
    printf("%d\n", ans);
    return 0;
}