题目链接:CF1409F「Subsequences of Length Two」 。
You are given two strings and consisting of lowercase Latin letters. The length of ttt is(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 and replace (the character at the position ) with some character from 'a'
to 'z'
.
You want to do no more than replacements in such a way that maximizes the number of occurrences of in 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.
The first line of the input contains two integers nnn and () — the length of and the maximum number of moves you can make. The second line of the input contains the string consisting of nnn lowercase Latin letters. The third line of the input contains the string consisting of two lowercase Latin letters.
Print one integer — the maximum possible number of occurrences of t in as a subsequence if you replace no more than characters in optimally.
4 2
bbaa
ab
3
7 3
asddsaf
sd
10
15 6
qwertyhgfdsazxc
qa
16
7 2
abacaba
aa
15
一般这种最优计数问题应该想到使用dp,但是 dp最困难的在于构造状态以及状态转移方程。对于这道题的dp 构造,蒟蒻的我毫无头绪,只好看比赛题解(Orz)。
构造出了转移方程后,最重要的是确定边界。首先易知的是对于第 2 和 3 个方程,要求 j<k;然后是初始条件 dp[0][0][0]=0。然而似乎u的边界不好确定,我们需要保证处理的都是可能出现的情况,所以需要将不可能的情况筛去,观察到每个转移方程的最优解都取决于子问题的最优解dp[i][j][u],因此,我们可以初始化数组 dp 所有元素值为 -1,然后根据初始条件往后拓展,在进行状态转移时,如果遇到的情况时,就直接跳过,因为这说明这种情况不能由初始情况 推导而来。
#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;
}