洛谷 P2679 子串()

前言

终极大考的最后一题是最难的(雾
好吧这题确实挺难。
打个广告:
蒟蒻的 Luogu UID 是 639563。
蒟蒻的 Atcoder 号是 heihei_harvey。
蒟蒻的 Codeforces 号是 harvey_wzy。

正文

题目传送门:$ \sum _ 1 ^ n a_i $

Level 1

大家对这种分关卡的题解评价怎样?
我们定义 $ f_{i, j, p, k} $ 为【A 的前 i 个字符】【选 p 个子串】【匹配 B 的前 j 个字符】【第 i 位选(k = 1)或不选(k = 0)】
晕了吗?

Level 2

当 $ a_i \ne b_j $ 时,我们可以得到

这部分还是很容易的吧?

Level 3

当 $ a_i b_j $ 时呢?
$ f_{i, j, p, 0} $ 还是一样,$ f_{i, j, p, 1} $ :

  • 选前面一个,跟这个连起来。$ f_{i – 1, j – 1, p, 1} $。
  • 选前面一个,不跟这个连起来。$ f_{i – 1, j – 1, p – 1, 1} $。
  • 不选前面一个。$ f_{i – 1, j – 1, p – 1, 0} $。

综上,状态转移方程为:

Level 4

但细想一下,空间会爆。
所以滚动一下。
另外这里处处都是模,一定要小心啊。

Level Boss

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

const int mod = 1000000007;
int f[2][205][205][2];

int main() {
	int n, m, k;
	cin >> n >> m >> k;
	string a, b;
	cin >> a >> b;
	a = ' ' + a;
	b = ' ' + b;
	f[0][0][0][0] = 1;
	f[1][0][0][0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			for (int p = 1; p <= k; p++) {
				if (a[i] == b[j]) {
					f[i & 1][j][p][0] = (f[(i - 1) & 1][j][p][0] + f[(i - 1) & 1][j][p][1]) % mod;
					f[i & 1][j][p][1] = ((f[(i - 1) & 1][j - 1][p][1] + f[(i - 1) & 1][j - 1][p - 1][0]) % mod + f[(i - 1) & 1][j - 1][p - 1][1]) % mod;
				} else {
					f[i & 1][j][p][0] = (f[(i - 1) & 1][j][p][0] + f[(i - 1) & 1][j][p][1]) % mod;
					f[i & 1][j][p][1] = 0;
				}
			}
		}
	}
	cout << (f[n & 1][m][k][0] + f[n & 1][m][k][1]) % mod;
	return 0;
}

你的EXP已经涨到了Lv.17 3000……
来吧!!!来实战PvT(Player v.s. Ti mu)吧!!!

————————

前言

终极大考的最后一题是最难的(雾
好吧这题确实挺难。
打个广告:
蒟蒻的 Luogu UID 是 639563。
蒟蒻的 Atcoder 号是 heihei_harvey。
蒟蒻的 Codeforces 号是 harvey_wzy。

正文

题目传送门:$ \sum _ 1 ^ n a_i $

Level 1

大家对这种分关卡的题解评价怎样?
我们定义 $ f_{i, j, p, k} $ 为【A 的前 i 个字符】【选 p 个子串】【匹配 B 的前 j 个字符】【第 i 位选(k = 1)或不选(k = 0)】
晕了吗?

Level 2

当 $ a_i \ne b_j $ 时,我们可以得到

这部分还是很容易的吧?

Level 3

当 $ a_i b_j $ 时呢?
$ f_{i, j, p, 0} $ 还是一样,$ f_{i, j, p, 1} $ :

  • 选前面一个,跟这个连起来。$ f_{i – 1, j – 1, p, 1} $。
  • 选前面一个,不跟这个连起来。$ f_{i – 1, j – 1, p – 1, 1} $。
  • 不选前面一个。$ f_{i – 1, j – 1, p – 1, 0} $。

综上,状态转移方程为:

Level 4

但细想一下,空间会爆。
所以滚动一下。
另外这里处处都是模,一定要小心啊。

Level Boss

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

const int mod = 1000000007;
int f[2][205][205][2];

int main() {
	int n, m, k;
	cin >> n >> m >> k;
	string a, b;
	cin >> a >> b;
	a = ' ' + a;
	b = ' ' + b;
	f[0][0][0][0] = 1;
	f[1][0][0][0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			for (int p = 1; p <= k; p++) {
				if (a[i] == b[j]) {
					f[i & 1][j][p][0] = (f[(i - 1) & 1][j][p][0] + f[(i - 1) & 1][j][p][1]) % mod;
					f[i & 1][j][p][1] = ((f[(i - 1) & 1][j - 1][p][1] + f[(i - 1) & 1][j - 1][p - 1][0]) % mod + f[(i - 1) & 1][j - 1][p - 1][1]) % mod;
				} else {
					f[i & 1][j][p][0] = (f[(i - 1) & 1][j][p][0] + f[(i - 1) & 1][j][p][1]) % mod;
					f[i & 1][j][p][1] = 0;
				}
			}
		}
	}
	cout << (f[n & 1][m][k][0] + f[n & 1][m][k][1]) % mod;
	return 0;
}

你的EXP已经涨到了Lv.17 3000……
来吧!!!来实战PvT(Player v.s. Ti mu)吧!!!