题解：P8392 [BalticOI 2022] Uplifting Excursion (Day1)

$0\sim 2n$ 共 $2n+1$ 个物品，第 $i$ 个体积为 $i-n$，有 $k_i$ 个，价值为 $1$，求体积和为 $m$ 的最大价值和。

二进制分组，将每次放在一起的 $2^x$ 个物品放在第 $x$ 层，设 $f_{x,i}$ 考虑到第 $x$ 层和之后的层，体积和为 $x2^i$ 的最大价值和。考虑到 $0\sim x-1$ 层体积之和在 $-(2n+1)2^{x+1} \sim (2n+1)2^{x+1}$ 之间，而答案要求 $m$，则在第 $x$ 层只用保留 $[m-(2n+1)2^{x+1},m+(2n+1)2^{x+1}]$ 之间的体积，对应到 $f_x$ 就是只有 $i\in [\frac{m}{2^x}-4n-2,\frac{m}{2^x}+4n+2]$ 是有用的。然后背包转移即可做到 $\mathcal O(n^3 \log k)$，常数太大可能过不了。