自动搬运

查看原文

来自洛谷，原作者为

	Exp10re My awAKen Dream.

搬运于2025-08-24 23:01:25，当前版本为作者最后更新于2024-07-31 15:17:22，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

挺恶心的分讨，被拿来当签到了。/kel

解题思路

感性理解可以发现：如果想让光标移动次数尽可能少，那么很有可能光标经过了某一行的行末。

为什么？因为从下一行的行末到这一行的行头只需要按一个键，却能使光标所在的列一次性增加一个很大的值。

那么，光标从起点到终点，要么不经过任意一行的行末，要么就经过其中至少一行的行末。

前者很好处理，接下来看看后者。

我们尝试维护从起点到每一行行末所需要的最少按键数，以及从每一行行末到终点所需要的最少按键数。

从起点到每一行行末的最少按键数，直观理解可以得到如下两种方案：

• 一直走到这一行，然后从当前位置一直按右键直到行末。
• 走到下一行的行头，然后按左键。

从起点左右扫一遍就可以 $O(n)$ 计算。

但是这种朴素的想法不是最优的，为什么？因为它没有最优化到达行头的时间。

如下所示：

$$\texttt{20,25,35,40,0}$$

假设我们在 $(4,20)$，想到达 $(3,36)$，最好的方案不是直接按 $19$ 次左键到达 $(4,1)$ 再左键到达 $(3,36)$，也不是先按上到达 $(3,20)$ 再按 $16$ 次右键到达 $(3,36)$，而是先按下到达 $(5,1)$，再按上到达 $(4,1)$，再左键到达 $(3,36)$。

由此我们可以得知：想到达一行的行头，我们可以先到达其他行的行末，再从这个行末到达其他行头。

那么我们可以从一个行末的最短路转移到其他行末的最短路。记到达第 $i$ 行行末的最少按键数量为 $cnt_i$，我们想转移到第 $j(j\leq i)$ 行的 $cnt_j$，则有：

$$cnt_j=\begin{cases} cnt_i+|i-j| & l_i=0\\ cnt_i+|i-j|+2 &l_i\ne 0\\ \end{cases}$$

对于 $j\gt i$ 也有：

$$cnt_j=\begin{cases} cnt_i+|i-j| & l_j=0\\ cnt_i+|i-j|+2 &l_j\ne 0\\ \end{cases}$$

注意上下两条的条件不同。

自行模拟就可以得到相同结论，故不作证明。

以上可以 $O(n)$ 递推转移。

接下来计算每一行行末到达终点的最小按键次数。

若位于第 $i$（$i\leq el$，在 $i\geq el$ 的情况同理）行行末，想要到达位于 $(el,ec)$ 的终点，记 $t=\min\limits_{i\lt j \lt el} l_j+1$，到达终点的最少按键数量为 $b_i$，则有：

$$b_i=\begin{cases} |l_i+1-ec|+|i-el| & t\geq l_i+1\\ |t-ec|+|i-el| & otherwise.\\ \end{cases}$$

不要忘了行末是可以一步到行头的，记得将 $b_i$ 与 $|i+1-el|+ec$（从第 $el$ 行的行头走到第 $ec$ 列）取 $\min$。

最后，不经过任何行末的答案与所有 $\min\limits_{1\leq i \leq n} cnt_i+b_i$ 取 $\min$ 即为最终答案。

期间需要计算区间 rmq，随便用一个数据结构维护就行了。

时间复杂度 $O(n\log n)$，瓶颈在区间 rmq。