题解：CF1409F Subsequences of Length Two

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 \neq t_1, t_2$ ，此时初值为 $dp_{i,j,l} = dp_{i-1,j,l}$ ；
$s_i \neq t_1, j \ge 1$ ，此时我们考虑将 $s_i$ 改为 $t_1$ ， $dp_{i,j,l} = \max (dp_{i,j,l}, dp_{i-1,j-1,l-1})$ ；
$s_i = t_1$ ，此时可以直接加个数， $dp_{i,j,l} = \max (dp_{i,j,l}, dp_{i-1,j,l-1})$ ；
$s_i \neq t_2, j \ge 1$ ，此时我们考虑将 $s_i$ 改为 $t_2$ 再加贡献， $dp_{i,j,l} = \max (dp_{i,j,l}, dp_{i-1,j-1,l} + l)$ ；
$s_i = t_2$ ，此时可以直接加贡献， $dp_{i,j,l} = \max (dp_{i,j,l}, dp_{i-1,j,l} + l)$ ；

但我们发现当

s_i = t_i

时，

t_1

也会有贡献，所以第二，三种真正的转移是需要加上

[t_1 = t_2] \times (l-1)

的，修改后的转移如下。

$s_i \neq t_1, j \ge 1$ 时， $dp_{i,j,l} = \max (dp_{i,j,l}, dp_{i-1,j-1,k-1} + [t_1 = t_2] \times (l-1))$ ；
$s_i = t_1$ 时， $dp_{i,j,l} = \max (dp_{i,j,l}, dp_{i-1,j,k-1} + [t_1 = t_2] \times (l-1))$ 。

当然也有从后向前记

t_2

加

t_1

贡献的方法，只不过倒过来转而已。

Code

CPP

#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;
}

题解：CF1409F Subsequences of Length Two

文章操作

Content

Solution

Code

相关推荐

评论

题解：CF1409F Subsequences of Length Two