6039
LOJ6039 「雅礼集训 2017 Day5」珠宝
LOJ 传送门 显然枚举物品做背包没有前途,于是我们把体积相等的物品捆绑在一起。 设 \(f_{i, j}\) 为考虑完体积 \(\in [1, i]\) 的物品,背包容量为 \(j\) 的最大值。可以贪心求出 \(g_{i, j}\) 为选 \(j\) 个体积为 \(i\) 的物品的价值最大值。 ......
LOJ #6039「雅礼集训 2017 Day5」珠宝
给定 $n$ 个物品,第 $i$ 个物品有体积 $c_i$,价值 $v_i$。给定 $K$,对 $1 \sim K$ 的所有 $i$ 求大小为 $i$ 的背包的最大价值。 $n \leq 10^6$,$K \leq 5 \times 10^4$,$c_i \leq 300$,$0 \leq v_i ......