P4141 消失之物 分析

· · 个人记录

对于原问题，这就是一个简单的计数 DP。设 f(i) 是将这些物品放进体积为 i 的背包内的方法数量，则转移方程是

f(i) = \begin{cases} 0 & i = -1 \\ 1 & i = 0 \\ \sum\limits_{j = 0}^{n} f(i - \min (w_j, i + 1)) & \text{otherwise} \end{cases}

写成代码便是

rep (i, 0, n) rrep (j, v, w[i]) dp[j] += dp[j - w[i]];

对于本问题，我们要求的是删除某个物品 i 后的最大容积。

明显我们有以下等式：

f(n) = f(n - w_0) + f(n - w_1) + \cdots f (n - w_{i}) + \cdots + f(n - w_k)

删除物品 i 后的 f(n) 应当减去 f(n - w_i)。于是，我们可以计算出去除了 i 后的 tp：

rep (i, 0, n) rep (j, 0, v + 1)
  if (j < w[i]) tp[j] = dp[j];
  else tp[j] = dp[j] - dp[j - w[i]];

这个复杂度是 O(nV) 的，显然能够通过。

编码时注意取模即可。