自动搬运

查看原文

来自洛谷，原作者为

	2huk Where should my destinaion be at? 我问我自己。

搬运于2025-08-24 23:17:32，当前版本为作者最后更新于2025-08-08 17:06:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

把所有点按颜色分层。那么必须先把上一层的车取完，才能取下一层的。于是考虑按照颜色层数 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)$。