题解 P4377 【[USACO18OPEN]Talent Show】

2018-10-09 21:32:05


感觉题解都不是很详细。

看题目那个式子:

$$\frac{\sum t_i}{\sum w_i}$$

显然是0/1分数规划。如果不懂,请Baidu。

按照基本法基本套路,二分一个 $L$ ,然后贪心地取 $t_i-L\cdot w_i$ ,判断是否为整数即可。

但是题目中有一个总质量至少为 $W$ 的条件,所以用01背包代替贪心,重量为体积, $t_i-L\cdot w_i$ 为价值,然后判断 $f[w]$ 是否为正即可。

注意体积可能会超出 $w$ ,这种情况下看做 $w$ 即可。

细节见代码