从2D1D到1D1D

从区间 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 的形式描述，以便优化。