题解：P12700 [KOI 2022 Round 2] 停车场

· · 题解

把所有点按颜色分层。那么必须先把上一层的车取完，才能取下一层的。于是考虑按照颜色层数 DP。

设 f(i) 表示，将所有层数 \le a_i 的车去除，且当前出口是点 i 的最小操作次数。

此时有一个很暴力的转移：预处理 g(i,j)（其中 a_i=a_j），表示从 i 开始，遍历完 a_i 层的所有点后，最终到达 j，最小操作次数。然后 f(lst) + w(lst,i)+g(i,j) \to f(j)，其中 a_i=a_j=a_{lst}+1。其中 w(i,j) 表示在环上从 i 走到 j 的最小步数，即 w(i,j)=\min(|i-j|,n-|i-j|)。

这样需要枚举 lst,i,j，复杂度肯定是不对的。但是我们先考虑 g(i,j) 的求解。走法一定是这样的：

即先从 i 走到某个点 x，然后从 x 转一圈（到 pre_x 或 nxt_x，即这一层中的上一个位置和下一个位置），最后到 j。

其实从上一层的 lst 走到 i 再走到 x 这个过程是冗余的。直接令 h(x) 表示，走完所有 <a_x 的点后，到达 x 的最小步数。

显然有：

h(x)+n-clockwise(x,nxt_x) \to f(nxt_x) \\ h(x)+n-clockwise(pre_x,x) \to f(pre_x)

其中 clockwise(i,j) 表示从 i 顺时针走到 j 的步数。

考虑 h(x) 的求解。枚举上一层的最后一个点：

h(x) = \min_{a_y = a_x-1}\left\{ f(y)+w(x,y) \right\}

即 f(y)+|x-y| 和 f(y)+n-|x-y| 的较小值。

不妨钦定 x\ge y。那么转移为 f(y)+x-y 和 f(y)+n-x+y 的较小值。把与 y 无关的项提出后是一个前缀和状物。

当然 x<y 同理。

那么 f,h 的转移都是 \mathcal O(1) 的。除离散化的时间复杂度为 \mathcal O(n)。