「CZOI-R3」消除序列题解
cybermage_liu
·
·
题解
思路
因为 b 数组每次只能左移 1 位，所以对于 a 的每个数字的操作顺序是固定的。
看到可以交换 x 和 y，求最小代价，那么当前的 x 和 y 有两种状态，可以和初始一样，也可以是交换后的。
不难想到 DP：
易得：
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)
初始 $f_{0,0}=0,f_{0,1}=z$，答案为 $\min(f_{n,0},f_{n,1})$。
那么怎么计算 $w1$ 和 $w2$ 呢？答案是树状数组。
因为右移不好处理，所以考虑开二倍空间，拆环为链。
那么这道题就做出来了，时间复杂度 $O(n\log n)$。
考虑到 $f$ 的转移状态只和上一次的有关，可以将其由二维数组转为两个变量，如下代码。
# AC code
```cpp
#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;
}
```