宝珠

20230918 P3188 [HNOI2007] 梦幻岛宝珠 Statement 01背包， \(n \le 100\)，但是容量 \(m \le 2^{30}\)。 物体的体积可以写成 \(a \times 2^b(a \le 10,b \le 30)\) Solution 发现 \(W\) 太 ......

这题的物品数量非常小，但是背包的重量非常大，我们采用压缩到二进制位来考虑，因为最多是n*20的数位*个数，并且上一位dp的状态不影响下一位。所以我们设计当前dp的状态为选取了前i位置时候所能获得的最大值。又因为上一维在数组dp时可能会被上一维的影响所以f[min(2*i+d,s)] =max(f[m ......

题目分析： 对于这种某一个值很大另一个值很小的背包题，就是要求找特殊性质。 既然每一个 $w$ 都可以写成 $a \times 2^b$ 的性质，就可以对于每一个 $b$ 单独做背包，这样的复杂度并不高，这样就可以得到 $f_{i,j}$ 表示第 $i$ 位选择 $j$ 个的最大价值。 对于背包合并 ......