1 条题解
-
0
[M] Candies(dp_m)题解
题意简述
个孩子,第 个分到 个糖,总数恰好为 ,求方案数 。
思路
朴素 DP
= 前 个孩子共分 个糖的方案数:
$$f_{i,x} = \sum_{y = \max(0,\,x-a_i)}^{x} f_{i-1,\,y}.$$朴素转移 ,总计 会超时。
前缀和优化
固定 后, 是 的一段滑动窗口和:
$$f_{i,x} = \text{pre}_{i-1}[x] - \text{pre}_{i-1}[\max(0, x-a_i) - 1],$$其中 。于是每层 ,总计 。
为什么正确
转移区间 的左右端点都随 单调右移,用前缀和差即可 得到区间和。转移只依赖上一层,倒序原地更新(或滚动数组)都安全。
复杂度
时间 ,空间 。
参考代码
#include <cstdio> #include <vector> using namespace std; const long long MOD = 1000000007LL; int main() { int n, k; scanf("%d %d", &n, &k); vector<long long> f(k + 1, 0), pre(k + 1, 0); f[0] = 1; for (int i = 0; i < n; i++) { int a; scanf("%d", &a); pre[0] = f[0]; for (int x = 1; x <= k; x++) pre[x] = (pre[x - 1] + f[x]) % MOD; for (int x = k; x >= 0; x--) { int lo = x - a; f[x] = (pre[x] - (lo > 0 ? pre[lo - 1] : 0) + MOD) % MOD; } } printf("%lld\n", f[k]); return 0; }易错点
pre必须在当前层算好再用;若边算f边改pre就错了(所以先算完整层pre)。pre[lo-1]的下标可能为 甚至负,要写成lo > 0 ? ... : 0。- 取模减法要加 MOD 防负数。
- 与 都是合法边界: 时答案为 (全 0 分配),样例 3 就是。
数据说明
共 19 组:4 组官方样例(含 与答案 ); 的 ; 的 与 ; 全 ; 全 、全 、随机六组。
- 1
信息
- ID
- 22
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者