ABC370E Avoid K Partition
Tag：DP
题目描述
给定一个长度为 \(n\) 的数组 \(a\)， 现在要把这个数组切割成若干个连续段。
规定合法的切割为不存在任何一段的和为 \(k\)， 问存在多少种合法的切割方案。
答案对 \(998244353\) 取模。
数据说明：
- \(2 \leq K \leq N \leq 2 \times 10^5\)
- \(1 \leq A_i \leq 10^4\)
分析
首先这个有一个较为简单的思路， 我们可以设计一个 \(dp[i]\) 表示在第 \(1\) 位到第 \(i\) 位有多少个合法的方案。
对于每一个 \(i\)， 我们都可以暴力从前面去转移， 以上的做法显然是 \(O(n^2)\) 的。
我们考虑一下是否存在方法可以优化这个 \(\text{DP}\)。
我们思考一下答案的本质，答案的本质实际上是全部情况减去了不合法的情况。 我们可以尝试在 \(\text{DP}\) 的过程中维护一个方案总数量，我们记为 \(sum\)。
既然我们有了总共的情况， 那么不合法的情况要如何减去呢？ 我们可以想到，在对数组做完前缀处理之后，记前缀数组为 \(pre\)。 假设当前位置的前缀和为 \(pre[i]\)， 如果前面存在一个位置的前缀为 \(pre[i] - k\) 的话， 那么这个位置就是不可转移的。
我们要如何做到快速查询 \(i\) 之前是否存在一个不可转移的位置？ 答案是我们可以用 \(map\) 来记录所有的前缀以及位置对应的合法方案数， 我们将这个 \(map\) 记为 \(mp\)。 当我们发现一个 \(map\) 里如果已经存在了一个值为当前前缀减去 \(k\) 的位置时， 我们这一步的 \(dp[i]\) 就可以使用 \(dp[i] = sum - mp[pre[i] - k]\) 来进行快速计算。 我们不难发现上述的式子中，当前位置的 \(sum\) 以及前缀都是可以随着 \(\text{DP}\) 的过程一起计算的， 所以我们只需要开一个 \(map\) 记录前缀和为不同的数值的时候有多少种方案。
上述做法的时间复杂度为 \(O(nlogn)\)。
代码实现
void NeverSayNever() {
int n,k; cin >> n >> k;
vector<int> vec(n+1);
for (int i = 1; i <= n ; ++i) {
cin >> vec[i];
}
for (int i = 1; i <= n ; ++i) {
vec[i] += vec[i-1];
}
map<int,int> mp;
mp[0] = 1;
int sum = 1;
vector<int> dp(n+1,0);
dp[0] = 1;
for (int i = 1; i <= n ; ++i) {
dp[i] = sum % MOD;
if(mp.contains(vec[i] - k)){
dp[i] = (dp[i] - mp[vec[i]-k] + MOD) % MOD;
}
sum = (sum + dp[i]) % MOD;
mp[vec[i]] = (mp[vec[i]] + dp[i]) % MOD;
}
cout << dp[n] % MOD << endl;
}
日志
本页面创建于 2024/09/09 14:34