【JZOJ4916】完全背包问题 题解

题目大意

  有 $n$ 种物品，体积分别为 $v_1,\cdots,v_n$，每种物品无限个。
  现在有 $m$ 次询问，每次询问给定一个容量为 $w$ 的背包，问是否存在一种物品选择方案，使背包恰好装满。同时，要求所选物品中，体积不小于 $L$ 的物品总数量不超过 $C$ 件。
  $n \le 50,\ \ m \le 10^5,\ \ w \le 10^{18}$
  $v_i \le 10000,\ \ L \le 20000,\ \ C \le 30$

题解

  设 $n$ 种物品中最小的是 $v_1$。
  若 $v_1 \ge L$，即全是大件物品，那么总体积不超过 $\max{v_i} \cdot C$，用暴力一点的 dp 搞掉。以下讨论 $v_1 < L$ 的情况。

  经典套路：设 $dp_{i,j}$ 表示：用了 $j$ 件大件物品和若干小件物品，使得体积 $\bmod v_1$ 等于 $i$ ，的最小体积。询问答案的时候直接看 $dp_{w\ \bmod\ v_1, 0\cdots C}$ 是否小于等于 $w$ 即可。（因为如果存在合法方案，那么这个合法方案去掉 $v_1$ 的物品之后必然满足总体积 $\le w$ 且体积 $\bmod v_1 = w \bmod v_1$ 且大件物品不超过 $C$）
  然后观察这个转移，我们选大件物品的话，转移到 $j+1$ 没什么问题，但是如果选小件物品，就会出现后效性，即这个转移路径是个环。
  这里有两种解决方法：第一种是把 dp 转移看成最短路问题，跑个 dijkstra 或者 spfa；第二种是，观察发现转移中出现的环都是简单环，假设是体积 $V_1 \to V_2 \to V_3 \to \cdots \to V_1$，那么这些 $V$ 中必有一个 dp 值最小的 $V_x$，它不可能从 $V_{x-1}$ 转移而来，这样就破环为链了，可以顺序 dp 了。