本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-18 10:46:01

$nk^2$ 显然。考虑优化。

转移有两种，一种是 $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$ 个单调队列中即可。