CF gym 103446I Steadily Growing Steam

CFgym103446I

若⼲物品具有体积 $t_i$ 和价值 $v_i$，选出⾄多 $k$ 件物品 将其体积翻倍，然后选出若⼲物品并将其分为体积和相同的两堆，问选出的物品价值之和最⼤是多少。

$n \leq 100$

周正：“这个题的状态定义是很经典的大家一定要记下来。”

我们首先定义一个暴力 DP ，设 $f_{i,s_1,s_2,k}$ 表示第 $i$ 个物品，第一个集合里分到体积为 $s_1$，第二个集合里分到体积为 $s_2$，已经翻倍了 $k$ 个物品的值，但是这样状态数达到了 $10^8$ 级别无法接受。

观察到这种两个东西相等的约束条件，实际上我们只关心他们的相对的差。不妨设 $f_{i,d,k}$ 表示第 $i$ 个物品，第一个集合里体积比第二个集合东西多了 $d$ ，已经翻倍了 $k$ 个物品的值。那么这样状态数就压下来了，接下来就考虑怎么 DP。

这个 DP 还是相对简单的背包，选⼊集合 1 的物品体积视为正，选⼊集合 2 的体积视为负，那么就有
$$
f_{i,d,k} = \min {
f_{i-1,d,k},
f_{i-1,d-v_i,k} +d_i,
f_{i-1,d+v_i,k} +d_i,
f_{i-1,d-2v_i,k-1} +d_i,
f_{i-1,d+2v_i,k-1} +d_i,
}
$$

第一维可以滚掉，时间复杂度 $O(n^3 \times \max t)$，记得 $d$ 那一维可能有负数，全部加上 $100$ 即可。

Code