P1047 · OFFICIAL SOLUTION

P1047 环锁解除官方题解

Gioush OJ · P1047 环锁解除

环锁解除

【题意简述】

两个长度为 $n$ 的排列位于环上。可以按两种方向旋转当前排列，经过尚未解除的位置分别产生 $x,y$ 的代价；可以支付 $z$ 交换两种方向的代价。目标符号按另一个排列给出的顺序解除，求最小总代价。

【Hint】

【提示】

只需要记录当前是否交换过两种方向的代价。用树状数组维护尚未解除的位置，动态查询两种方向经过的位置数量。

【数据点 1∼51\sim 51∼5】

当 $n\leq 10$ 时，可以把当前控制位、已经解除的符号集合以及 $x,y$ 是否交换作为状态，使用最短路枚举旋转、交换与免费解除操作。状态数为 $\mathcal{O}(n2^n)$ 。

【数据点 6∼106\sim 106∼10】

特殊性质满足 $x=y=z$ 。交换不会改变旋转代价，额外交换只会增加代价，因此可以忽略交换。每次比较顺时针与逆时针到达下一个目标时经过的尚未解除位置数量，取较小值即可。

【数据点 11∼1911\sim 1911∼19】

当 $n\leq 10^3$ 时，可以直接沿环向两个方向扫描，计算到达下一个目标前经过的尚未解除位置数量。每次转移为 $\mathcal{O}(n)$ ，总时间复杂度为 $\mathcal{O}(n^2)$ 。

这一档已经保留了正解中的两个 DP 状态，瓶颈只在于动态距离的计算。

【正解】

设 $d_{i,0}$ 表示已经按顺序解除前 $i$ 个符号，当前旋转代价仍为 $(x,y)$ 时的最小代价；设 $d_{i,1}$ 表示已经解除前 $i$ 个符号，当前旋转代价为 $(y,x)$ 时的最小代价。

初始状态为

d_{0,0}=0, \qquad d_{0,1}=z.

从符号 $b_{i-1}$ 的位置移动到 $b_i$ 的位置。记顺时针经过的尚未解除位置数量为 $l_i$ ，逆时针经过的数量为 $r_i$ 。已解除位置不再产生代价，所以这两个量必须动态维护。

把每个尚未解除的位置记为 $1$ ，并把环复制一遍。树状数组支持区间求和与单点删除，从而在 $\mathcal{O}(\log n)$ 时间得到 $l_i,r_i$ 。

保持原方向时有

d_{i,0}=\min\left\{ \begin{aligned} &d_{i-1,0}+l_ix,\\ &d_{i-1,0}+r_iy,\\ &d_{i-1,1}+l_iy+z,\\ &d_{i-1,1}+r_ix+z. \end{aligned} \right.

保持交换状态时有

d_{i,1}=\min\left\{ \begin{aligned} &d_{i-1,1}+l_iy,\\ &d_{i-1,1}+r_ix,\\ &d_{i-1,0}+l_ix+z,\\ &d_{i-1,0}+r_iy+z. \end{aligned} \right.

每一项唯一对应本次旋转方向与是否交换，因此转移覆盖全部合法方案。另一方面，任意合法操作序列在解除第 $i$ 个符号时也必然落入其中一项，所以没有遗漏。答案为

\min(d_{n,0},d_{n,1}).

【复杂度分析】

每个符号只进行常数次树状数组查询与修改。时间复杂度为 $\mathcal{O}(n\log n)$ ，空间复杂度为 $\mathcal{O}(n)$ 。

【参考代码】

1/*2Author:Ehundategh3Date:2026/7/304Name:circle.cpp5You steal,I kill.6*/7#include <cstdio>8#include <cstring>9#include <algorithm>10#define MAXN 100001011using namespace std;12 13int lowbit(int x){return x&-x;}14 15int c,T,n,x,y,z,Pos[MAXN];16long long C[MAXN<<1],a[MAXN],b[MAXN],Dp[MAXN][2];17void Update(int Now,int Val){for(;Now<=2*n;Now+=lowbit(Now)) C[Now]+=1ll*Val;}18long long Query(int Now){long long Ret=0;for(;Now;Now-=lowbit(Now)) Ret+=C[Now];return Ret;}19 20long long GetD(int l,int r){21    if(l>r) r+=n;22    if(r-l>=n) r-=n;23    return Query(r)-Query(l-1);24}25 26void Solve(){27    scanf("%d%d%d%d",&n,&x,&y,&z);28    for(int i=1;i<=2*n;i++) C[i]=lowbit(i);29    for(int i=1;i<=n;i++) scanf("%lld",&a[i]),Pos[a[i]]=i;30    for(int i=1;i<=n;i++) scanf("%lld",&b[i]);31    Pos[0]=1;32    Dp[0][0]=0;33    Dp[0][1]=z;34    for(int i=1;i<=n;i++){35        int dl=GetD(Pos[b[i-1]],Pos[b[i]])-GetD(Pos[b[i]],Pos[b[i]]);36        int dr=GetD(Pos[b[i]]+1,Pos[b[i-1]]+n);37        Dp[i][0]=min(min(Dp[i-1][0]+1ll*dl*x,Dp[i-1][0]+1ll*dr*y),min(Dp[i-1][1]+1ll*dl*y+z,Dp[i-1][1]+1ll*dr*x+z));38        Dp[i][1]=min(min(Dp[i-1][1]+1ll*dl*y,Dp[i-1][1]+1ll*dr*x),min(Dp[i-1][0]+1ll*dl*x+z,Dp[i-1][0]+1ll*dr*y+z));39        Update(Pos[b[i]],-1);40        Update(Pos[b[i]]+n,-1);41    }42    printf("%lld\n",min(Dp[n][0],Dp[n][1]));43}44 45int main(){46    scanf("%d%d",&c,&T);47    while(T-->0) Solve();48    return 0;49}