传送门
f[i][j]表示前i个物品，容量为j的方案数
c[i][j]表示不选第i个物品，容量为j的方案数
两个数组都可以压缩到一维
那么f[i][j] = f[i 1][j] + f[i 1][j w[i]] （不放i与放i）
c数组的转移分多种情况
1.j < w[i]时，说明当前物品放不开，那么c[i][j] = f[n][j]
2.j >= w[i]，c[i][j] = f[n][j] c[i][j w[i]]
因为c[i][j]表示不选物品i，容量为j的方案数，等于总的方案数减去选物品i，容量为j的方案数
而选物品i，容量为j的方案数就等于不选物品i，容量为j w[i]的方案数，也就是补集
#include <cstdio> #include <iostream> #define N 2001 int n, m; int f[N], c[N], w[N]; //f[i][j]表示前i个物品，容量为j的方案数 //c[i][j]表示不选第i个物品，容量为j的方案数 //两个数组都可以压缩到一维 inline int read() int main() for(i = 1; i <= n; i++) return 0; }
上一篇：[BZOJ3545] [ONTAK2010]Peaks（线段树合并 + 离散化）
下一篇：[BZOJ1582] [Usaco2009 Hol]Holiday Painting 节日画画（线段树）
DP
