[ABC376F] Hands on Ring (Hard)

zrl123456 · 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），问所有操作结束之后最少移动多少次。
数据范围：

• ## 做法 ### 朴素 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)。

代码

这呢