题解 | E - Removal

E - Removal

首先不考虑去重，可以写出以下 DP，设 表示不去重情况下，考虑前 个数字，删除了 个，且最后一个为数字为 的方案数，有如下转移：

然后拿着这个东西取跑一遍样例，果真是错的，然后研究一下 DP 值，看看重复的都是什么情况。

这里以第一个样例为例，重复的点为去除前两个和后两个的两种情况，从 DP 转移的角度观察这个问题，当 的时候，我们考虑 和 的情况：

m = 1: 子序列为 "1" 或 "2"
m = 2: 子序列为 ""

然后到了 ，我们会从 转移出一个 "1"，从 转移出一个 "1"，两个就重复了。

思考归纳一下，设两个序列为 pre 和 pre+s[i + 1] 那么前一种情况加上 ，后一种情况不加，就会出现重复。

所以去重的操作就是：

int n, m, k, s[N]; mint dp[N][11][11];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	while (cin >> n >> m >> k) {
		forn (i, 1, n) cin >> s[i];
		dp[1][0][s[1]] = 1;
		dp[1][1][0] = 1;
		rep (i, 1, n) forn (j, 0, m) {
			if (j) dp[i + 1][j][s[i + 1]] -= dp[i][j - 1][s[i + 1]];
			forn (t, 0, k) {
				dp[i + 1][j][s[i + 1]] += dp[i][j][t];
				if (j < m) dp[i + 1][j + 1][t] += dp[i][j][t];
			}
		}
		mint ans = 0;
		forn (t, 0, k) ans += dp[n][m][t];
		cout << ans.r << '\n';
		forn (i, 1, n) forn (j, 0, m) forn (t, 0, k) 
			dp[i][j][t] = 0;
	}
	return 0;
}