P4182 [USACO18JAN] Lifeguards P

· · 个人记录

转移有两种，一种是 $r_k \lt l_i$ 的，转移是 `dp[k][j - i + k + 1] + r[i] - l[i]`。 另一种是 $r_k \ge l_i$ 的，转移是 `dp[k][j - i + k + 1] - r[k] + r[i]`。 由于我们把包含的区间删掉了，因此 $l$ 随 $r$ 增。因此，我们可以用单调队列维护第二种转移的最大值。从队头弹的时候，我们知道这个点会变成第一种转移，维护一个最大值就好了。 但是，我们状态的第二维怎么处理？第二维是 $j - i + 1 + k$，因此我们可以对于每一个 $j - i + 1$，维护出 `dp[k][k + t]` 的最大值，放到 $n$ 个单调队列中即可。