P10803 [CEOI2024] 文本编辑器 题解

Exp10re · 2024-07-31 15:17:22 · 题解

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

解题思路

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

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

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

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

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

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

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

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

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

如下所示：

假设我们在 (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，则有：

对于 j\gt i 也有：

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

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

以上可以 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 与 |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。