atdpx Tower

__ryp__ · 2024-09-24 16:48:41 · 个人记录

考虑证明按照 s + w 贪心的正确性。

我们的贡献和位置是无关的，因此我们要证的仅仅是当 s_i + w_i \lt s_j + w_j 时，若 j 可以放在 i 上头，那么 i 就一定能放在 j 上头。也就是说：任意一种方案，都可以是排序后顺序构造。

设 p_i 表示当前方案中 1 到 i 所有箱子的重量和，那么我们已知 p_{i-1} \le s_i, p_{j-1}\le s_j，要证 p_{i-1}\le s_j, p_{j-1} - w_i + w_j \le s_i。

放缩代入得证。