Yet Another Many Moves Problem.

· · 题解

写了个垃圾做法，看来我对 Many Moves 的理解还不够深刻。

从小往大扫时间。这个问题没有后效性，考虑 dp。

记 y_{i,j} 表示时刻 i 的第 j 个音符所在位置，其中 j\in \{1, 2\}。注意到在第 i 个时刻，为了完成要求，一定有一只手会移动到 y_{i,1} 这个位置，并且为了保证花费最小，在当前时刻一定不会再移动这只手。所以设 f_{i,j} 表示在第 i 个时刻，从初始状态依次完成前 i 个要求，最后两只手分别位于 y_{i,1} 和 j 的最小花费。那么答案就是 \min\limits_{j=1}^nf_{m,j}。

记 \operatorname{dis}(i,j) 为 i,j 两点的环上距离，显然 \operatorname{dis}(i,j)=\min\{|i-j|,n-|i-j|\}。

考虑转移。枚举 i-1 时刻另一只手在哪个位置，记为 k。

若 i 时刻只有一个音符，那么考虑两只手分别怎么移动，有：

f_{i,j}=\min\limits_{k=1}^n\min\{f_{i-1,k}+\operatorname{dis}(k,j)+\operatorname{dis}(y_{i-1,1},y_{i,1}),f_{i-1,k}+\operatorname{dis}(k,y_{i,1})+\operatorname{dis}(y_{i-1,1},j)\}

注意到 f_{i,j}+\operatorname{dis}(j,k)\ge f_{i,k}。因为 f_{i,j} 表示从初始状态开始依次完成前 i 个要求后，最终两只手位于 y_{i,1} 和 j。加上 \operatorname{dis}(j,k) 后就是再从 j 走到 k，相当于完成了一个这样的过程：从初始状态开始依次完成前 i 个要求，最终两只手位于 y_{i,1} 和 k。而 f_{i,k} 表示该过程的最小花费，所以上式自然成立。

那么转移方程可以改写成：

f_{i,j}=\min\{f_{i-1,j}+\operatorname{dis}(y_{i-1,1},y_{i,1}),f_{i-1,y_{i,1}}+\operatorname{dis}(j,y_{i-1,1})\}

若 i 时刻有两个音符，仍可用上式求出 f_{i,y_{i,2}}。其他的位置不能这样求因为不能保证转移的过程中经过了 y_{i,2}。

注意我们状态的定义，其应当满足这个状态完成了前 i 个要求。所以对于剩余位置 j，f_{i,j} 对应的移动方案一定可以划分为两个部分：先完成前 i 个要求且两只手恰好在 y_{i,1} 和 y_{i,2}，再 y_{i,2} 那只手移动到 j。所以有：f_{i,j}=f_{i,y_{i,2}}+\operatorname{dis}(y_{i,2},j)。

扫描 i 的过程中用一个数据结构维护当前的所有 f_j。转移都是区间操作的形式，考虑使用线段树维护。

将环上距离拆开可以发现，我们要支持的其实是以下几种操作：

每个位置维护一个三列的矩阵，则上述操作可以轻松使用 (\min,+) 矩阵乘法实现。不过可以注意到只有三个位置是有用的，因此可以只记录那三个位置的信息，这样常数小一点。

认为 n,m 同阶，时间复杂度 \mathcal{O}(m\log n)，空间复杂度 \mathcal{O}(n)。