20230918
P3188 [HNOI2007] 梦幻岛宝珠
Statement
01背包， \(n \le 100\)，但是容量 \(m \le 2^{30}\)。
物体的体积可以写成 \(a \times 2^b(a \le 10,b \le 30)\)
Solution
发现 \(W\) 太大了，而 \(a,b\) 又很小，
那我们考虑对背包进行分组。
用 \(f_{i,j}\) 维护第 \(i\) 组容量为 \(j \times 2^i\) 的答案。
每一组就直接用普通背包做就可以了。
现在考虑如何合并？
从 \(2^{i-1}\) 转移到 \(2^i\) 时，我们同样用 \(f_{i,j}\) 表示 \(2^{0 \sim i}\) 位， \(j \times 2^i\) 时的答案。
我们考虑可以从 \(2^{i-1}\) 那里拿一些上来，
假设拿上来 \(k \times 2^i\) ，于是：
\[f_{i,j}=\max_{k=0}^{j}\{ f_{i-1,k \times 2+[W\&(1<<(i-1))]}+f_{i,j-k}\}
\]
其中 \([W\&(1<<(i-1))]\) 是如果 \(W\) 里面本来可以有 \(2^{i-1}\) ，
我就可以多拿上来一个。
于是这道题就做完了。
时间复杂度 \(O(T \times len \times 1000 \times 1000)\)
Conclusion
这道题有特殊性质，我们可以考虑把它分组。
在合并的时候注意上一个带上来的贡献……
思路还是挺妙的~