[BZOJ2287]【POJ Challenge】消失之物（DP）

传送门

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（线段树合并 + 离散化）

下一篇：[BZOJ1579] [Usaco2009 Feb]Revamping Trails 道路升级（分层图最短路 + 堆优化dijk）

---

DP