本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-10-22 17:41:43

题目

[ABC376F] Hands on Ring (Hard)

题目考察：dp。
题目简述：
有一个有 $n$ 个节点的环，一开始你的两只手分别在 $1$ 节点和 $2$ 节点，每次你的手可以移动到相邻两个节点（即假设原来在 $x$ 处，那么就能移动到 $(x+n-2)\bmod n+1$ 和 $x\bmod n+1$），前提是另一只手不在将要移动的格子上。
有 $q$ 次操作，每次操作（$h_i,t_i$）要求你将左手或右手（$h_i$）移到某一个格子（$t_i$），问所有操作结束之后最少移动多少次。
数据范围：

• $3\le n\le 3000$。
• $1\le q\le 3000$。
• $\forall i\in[1,n],h_i$ 要么是 L，要么是 R。
• $1\le t_i\le n$。

做法

朴素 dp

显然，我们可以得到一个状态为 $\Theta(n^2q)$ 的 dp，设 $f_{i,j,k}$ 为第 $i$ 次操作中左手放在了 $j$ 节点，右手放在了 $k$ 节点，转移方程为（$\text{dist}(x,y,z)$ 表示在不经过 $z$ 点的情况下，从 $x$ 到 $y$ 的距离）：
$$f_{i,j,k}=\min_{j_0=1}^n(\min_{k_0=1}^n(f_{i-1,j_0,k_0}+\min(\text{dist}(j_0,j,k_0)+\text{dist}(k_0,k,j),\text{dist}(k_0,k,j_0)+\text{dist}(j_0,j,k))))$$ 但是每个状态都需要 $\Theta(n^2)$ 转移，时间复杂度（$\Theta(qn^4)$）不可接受（尽管能用滚动数组滚掉第一位）。

证明

证明先移动一个手再移动另一个手更优。
分类讨论：

1. 如果另一只手挡住了这只手的运动路线，直接将另一只手移到一个位置就行了。
2. 否则另一只手不动就行了。

于是我们想到了后面的优化。

优化 $1$

我们发现，实际上有意义的状态并不多，第 $i$ 次操作你的一只手一定要在 $t_i$ 节点上，这样的话有意义的状态就变成了 $\Theta(n)$ 个，但时间复杂度仍然是 $\Theta(qn^3)$。

优化 $2$

我们又发现，有意义的状态只有 $\Theta(n)$ 个，所以我们不需要 $\Theta(n^2)$ 枚举上一个状态，直接用 map 或直接压维的方式解决，时间复杂度为 $\Theta(qn^2)$（可能带 $\log$）。

优化 $3$

我们又双叒叕发现，每个上一个状态只会出现 $1$ 个第 $2$ 种情况，于是我们换种方式转移（我不会告诉你我忘了叫什么了）。
这样每次操作的有效状态为：$dp_{i,i-1}$ 和 $dp_{i,i+1}$（所有的上一个的有效状态均可转移），其他的 $dp_{i,j}$（一个有效状态只会转移一个）。
时间复杂度为 $\Theta(qn)$。

代码

这呢