不想动脑子 || solution - CF294B

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

但是我不想动脑子。

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

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

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

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

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

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

华风夏韵，洛水天依！