# CF1409F「Subsequences of Length Two」

## 1. 题目

### 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.

## 2. 题解

### 分析

• 首先定义状态：$dp(i,j,u)$ 表示处理完字符串 $s$ 的第 $i$ 个字符后，已经使用了 $j$$move$ 操作，且字符串 $s[0..i-1]$ 中有 $u$ 个字符 $t$，此时字符串 $s[0..i-1]$ 中包含的子序列 $t$ 的最大个数。

• 然后构造状态转移方程：设 $e_0 = 1$ 表示 $s[i] = t$，否则 $e_0 = 0$；设 $e_1 = 1$ 表示 $s[i] = t$，否则 $e_1 = 0$；设 $e_{01} = 1$ 表示 $t = t$，否则 $e_{01} = 0$

1. 如果不处理第 $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}$

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

$\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}$

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

$\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}$