不想动脑子 || solution - CF294B

· · 题解

为什么题解区都是这么难理解的 dp 做法呀……

但是我不想动脑子。

Solution 1

显然我们在设状态的时候可以添加限制，设 f_{i,j} 为前 i 都必须选，下层厚度之和为 j，这时上层宽度之和的最小值。转移考虑一本书放在上层还是下层即可，有式子：

f_{i,j} = \min \begin{cases} f_{i-1,j} + w_i \\ f_{i-1,j-t_i} \end{cases}

答案就是最小满足 j \ge f_j 的 j。

时间复杂度 O(n^2)。

Solution 2

还有一个更无脑的做法，甚至复杂度更优秀。

发现 t_i 的取值只有 1,2，所以当下层厚度之和确定的时候，是容易计算上层最小宽度的。具体地，按照 t_i 的取值分开，然后分别排个序，贪心把宽度大的放到下面，双指针维护即可。

于是就可以二分答案了，复杂度只有 O(n \log n)。

华风夏韵，洛水天依！