题解：AT_agc072_a [AGC072A] Rhythm Game

BPG_ning · 2025-11-12 14:48:43 · 题解

首先把问题转化成：[T_i-X_i,T_i+X_i+D] 时间内可以以 2X_i 的时间做任务，要求判断能否做完全部任务。

若只有任务的上界是简单的，按照 T_i+X_i 从小到大做就是对的，证明考虑若不是按这个顺序做的话，交换顺序后仍然合法。

考虑有下界。还是按照 T_i+X_i 排序，若我们跳过了一些小的去做一个大任务的 i，对于没做的小的任务 j，有 T_j-X_j<T_j+X_j\leq T_i+X_i= T_i-X_i+2X_i\leq \text{start}+2X_i。意味着此时所有小的任务的下界都没了，那么按照上述贪心做就是对的，证明类似。

然后就是简单的了。发现对于任意时刻做完了的任务构成一个前缀加上后面的一个单点，设 f_{i,j} 表示做完的任务是 1,2\cdots,i,j 的最小时间，转移是 O(1) 的。

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