从区间 DP 到线性 DP
题目
你有 $n$ 个区间，每个区间是 $l,r,w$ 三个参数描述，表示左右端点和权值，如果区间有交（包括端点），那么就在有交的两个区间连边，形成一张无向图，有个参数 $k$，你需要删去一些区间，使得每个联通块大小不超过 $k$。
$n\leq 500$
$n\leq 2500$
思考
首先这肯定不是一个图论问题，给一张图做这个问题是 $NP$ 的，所以要利用好区间的性质。
先把区间离散化。
发现可以考虑一段区间 $[l,r]$，只考虑在区间内的区间，计算其答案，有两种方式，第一种是将区间继续划分成两个子区间，划分区间的过程，体现出了全局最优的思想，即我们假定了当前区间内的所有线段全部联通，这样不一定能在此处取到最优解，但一定可以在向下动态规划的过程中得到最优解，另一种是直接在当前区间选最大的 $k$ 个保留。
划分区间的方式，就是选一个地方断开，删掉越过这个地方的所有区间，变成两个子问题。
有了这样的思路，我们很容易设计出一个 $O(n^3)$ 的区间动态规划出来。
优化
$O(n^3)$ 可以通过 $n\leq 500$ 的数据点，但是无法通过 $n\leq 2500$，所以需要优化为 $O(n^2)$，其中预处理 $[l,r]$ 的复杂度是 $O(n^2\log n)$ 的，但是常数较小能够接受。
于是可以考虑利用区间 $dp$ 的一些常见优化手段，打个表，发现决策点并不单调，所以对于这类 $2D1D$ 问题我们有点束手无策。但是感觉上记录区间有点浪费，于是考虑能不能线性的搞出来。发现如果设 $dp[i]$ 表示考虑前 $i$ 个的答案，从 $j<i$ 转移，$[j,i]$ 采用直接减少到 $k$ 的方式，也能得到和区间DP方式相同的转移考虑。
所以被优化成了 $O(n^2)$。越过每个点的区间总数，是可以动态维护的，均摊 $O(1)$。
从2D1D到1D1D
其实这类问题，是伪区间DP问题，比较它和真区间DP问题，比如《石子合并》，《优雅的闪电》的差异。它本质上是 1D1D 问题，石子合并很明显就是需要体现区间合并的顺序，所以必须采用区间DP。优雅的闪电的转移，无法被 1D1D 的转移考虑完全，所以仍然需要区间 DP。
关于一些 2D1D 的问题，可以仔细考察它的转移，能否被 1D1D 的形式描述，以便优化。