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

 京公网安备 11010502036488号
京公网安备 11010502036488号