自动搬运

查看原文

来自洛谷，原作者为

	cybermage_liu 十年星空见，一剑天地开。

搬运于2025-08-24 23:15:19，当前版本为作者最后更新于2025-05-05 09:08:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

思路

因为 $b$ 数组每次只能左移 $1$ 位，所以对于 $a$ 的每个数字的操作顺序是固定的。

看到可以交换 $x$ 和 $y$，求最小代价，那么当前的 $x$ 和 $y$ 有两种状态，可以和初始一样，也可以是交换后的。

不难想到 DP：

• $f_{i,0}$ 表示对于前 $i$ 个数，$x$ 和 $y$ 在执行完第 $i$ 个操作后与初始状态相同的最小代价。
• $f_{i,1}$ 表示对于前 $i$ 个数，$x$ 和 $y$ 在执行完第 $i$ 个操作后与初始状态不同的最小代价。

易得：

$$f_{i,0}=\min(f_{i-1,0}+w1\times x,f_{i-1,0}+w2\times y,f_{i-1,1}+w1\times x+z,f_{i-1,1}+w2\times y+z) \\ f_{i,1}=\min(f_{i-1,0}+w1\times y+z,f_{i-1,0}+w2\times x+z,f_{i-1,1}+w1\times y,f_{i-1,1}+w2\times x) $$

$w1$ 表示将 $b_i$ 在 $a$ 中的位置左移到当前第一个位置的经过的没有操作过的数的个数，$w2$ 同理，表右移。

初始 $f_{0,0}=0,f_{0,1}=z$，答案为 $\min(f_{n,0},f_{n,1})$。

那么怎么计算 $w1$ 和 $w2$ 呢？答案是树状数组。

因为右移不好处理，所以考虑开二倍空间，拆环为链。

那么这道题就做出来了，时间复杂度 $O(n\log n)$。

考虑到 $f$ 的转移状态只和上一次的有关，可以将其由二维数组转为两个变量，如下代码。

AC code

#include<bits/stdc++.h>
#define int long long
#define lowbit(i) (i&-i)
using namespace std;
const int N=2e6+5;
int a[N],b[N],t[N],p[N],n;
//树状数组
void change(int x,int y){
	for(int i=x;i<=2*n;i+=lowbit(i)) t[i]+=y;
}
int query(int x){
	int res=0;
	for(int i=x;i;i-=lowbit(i)) res+=t[i];
	return res;
}
int query_(int x,int y){
	if(x>y) y+=n;//特殊处理避免出错
	if(y-x>=n) y-=n;
	return query(y)-query(x-1);
}
signed main(){
	int x,y,z,l=1;//l 为当前第一个数在原序列中的位置 
	cin>>n>>x>>y>>z;
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]),p[a[i]]=i;//p 存位置 
	for(int i=1;i<=n;i++) scanf("%lld",&b[i]);
	for(int i=1;i<=2*n;i++) change(i,1);
	int f1=z,f0=0;//注意 f1 初始为 z 
	for(int i=1;i<=n;i++){
		int w1=query_(l,p[b[i]])-query_(p[b[i]],p[b[i]]);
		int w2=query_(p[b[i]]+1,l+n);
		int f00=f0,f11=f1;
		f0=min(min(f00+w1*x,f00+w2*y),min(f11+w1*x+z,f11+w2*y+z));
		f1=min(min(f00+w1*y+z,f00+w2*x+z),min(f11+w1*y,f11+w2*x));
		//更新树状数组和 l 
		change(p[b[i]],-1);
		change(p[b[i]]+n,-1);
		l=p[b[i]];
	}
	cout<<min(f0,f1);
	return 0;
}