P12406 「CZOI-R3」消除序列 题解

我的方法使用了动态规划和树状数组，可能并不简洁，但题解太简略了，我暂时也不清楚怎么简单地维护题解里的 $u$ 和 $v$，其他部分是原题解的详细版本。

首先分析一下操作（方便描述，标了个号）：

1. 将 $a$ 循环左移一位。若在进行操作前 $a_1\neq 0$，则消耗 $x$ 点代价。
2. 将 $a$ 循环右移一位。若在进行操作前 $a_1\neq 0$，则消耗 $y$ 点代价。
3. 交换 $x,y$。消耗 $z$ 点代价。
4. 若 $a_1=b_1$，将 $b$ 循环左移一位，同时令 $a_1=0$。不消耗代价。

题目中出现了大量的循环位移操作，实际上可以对其进行简化分析，因为题目要求把 $a$ 清空，那么我们将每一个 $4$ 操作当作一个阶段，于是，题目要求按照 $b$ 数组的顺序完成 $n$ 个阶段的操作，每个阶段消掉一个数字，消掉数字的顺序就是 $b$ 数组的顺序（这样，操作 $4$ 中的循环移位解决掉了）。

移动整个数组并不好处理，因此可以理解为移动环上的指针。于是转化 $1$ 和 $2$ 操作，最后的描述可以变为：

令指针 $p$ 指向 $a_1$。有如下操作：

1. 将指针右移一位，若原指向点不为 $0$，消耗 $x$ 点代价。
2. 将指针左移一位，若原指向点不为 $0$，消耗 $y$ 点代价。
3. 交换 $x,y$。消耗 $z$ 点代价。
   指针要依次移动到 $b$ 数组标记的每一个位置，完成 $n$ 个阶段。

注意：移动指针与移动数组相反；指针在 $0$ 的移动没有代价！

那么，先把每一个阶段要求到达的位置处理出来，这样就没有两个数组了。因为都是排列，所以可以把 $a$ 中数字位置处理到 $p$ 数组，即 p[a[i]]=i，再把 $b$ 中的每一个数字对应成 $a$ 中的位置，按顺序记录，详见代码。

入手点是 $3$ 操作，可以发现，在每一个阶段，一定只会使用 $1$ 和 $2$ 操作中的一种，操作 $3$ 至多 $1$ 次且在开始（将结尾的操作 $3$ 归为下一阶段）。考虑到只有操作 $3$ 有后效性，利用它来设计状态：

• $dp_{0,i}$ 表示进行过偶数次操作 $3$，这时 $1$ 和 $2$ 操作代价和开始时一样。
• $dp_{1,i}$ 表示进行过奇数次操作 $3$，这时 $1$ 和 $2$ 操作代价和开始时相反。

设计转移（这应该是比较好想的）：

• $dp_{0,i}=\max\{dp_{0,i-1}+steps_{left}\times x,dp_{0,i-1}+steps_{right}\times y,dp_{1,i-1}+steps_{left}\times y+z,dp_{1,i-1}+steps_{right}\times x+z\}$
• $dp_{1,i}=\max\{dp_{1,i-1}+steps_{left}\times y,dp_{1,i-1}+steps_{right}\times x,dp_{0,i-1}+steps_{left}\times x+z,dp_{0,i-1}+steps_{right}\times y+z\}$

设计边界：

• $dp_{0,1}=0$
• $dp_{1,1}=z$

这里重点处理 $steps_{left}$ 和 $steps_{right}$，具体地，每一个 $0$ 位置都不算贡献，要求一种可以动态修改和区间查询的数据结构，想到线段树和树状数组。但是在比赛中，线段树由于常数问题（也许）被卡掉了，改用了树状数组，具体逻辑就是把未清空的位置设为 $1$，清空后改为 $0$，用区间和处理步数，详见代码。

输出的答案便是 $\min\{dp_{0,n},dp_{1,n}\}$ 了。

代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,x,y,z;
struct BIT{
  int t[2000006],tot;
  void init(){
    memset(t,0,sizeof(t));
    tot=0;
  }
  void add(int i,int val=1){
	  if(i==0)return;
    tot++;
    for(;i<=n;i+=(i&-i)){
      t[i]+=val;
    }
  }
  int query(int i){
    int s=0;
    for(;i;i-=(i&-i)){
      s+=t[i];
    }
    return s;
  }
}bit;
int a[1000006],p[1000006];
int dp[2][1000006];
int q(int l,int r){
	return bit.query(r)-bit.query(l-1);
}
int left(int now,int to){
//	return now>=to?now-to:n+now-to;
//	return now>=to?SegTree.query(1,to+1,now):SegTree.query(1,1,now)+SegTree.query(1,to+1,n);
	return now>=to?q(to+1,now):q(1,now)+q(to+1,n);
}
int l1(int x){
	return x-1==0?n:x-1;
}
int right(int now,int to){
//	return now<=to?to-now:n+to-now;
//	return now<=to?SegTree.query(1,now,to-1):SegTree.query(1,now,n)+SegTree.query(1,1,to-1);
	return now<=to?q(now,to-1):q(now,n)+q(1,to-1);
}
int r1(int x){
	return x+1==n?1:x+1;
}
void solve(){
	scanf("%lld%lld%lld%lld",&n,&y,&x,&z);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		p[a[i]]=i;
//		SegTree.dat[i]=1;
	}
//	SegTree.build(1,1,n);
	bit.init();
	for(int i=1;i<=n;i++){
		bit.add(i);	
		int tmp;
		scanf("%lld",&tmp);
		a[p[tmp]]=i;
	}
	for(int i=1;i<=n;i++){
		p[a[i]]=i;
	}
	p[0]=1;
	dp[0][1]=0;
	dp[1][1]=z;
	for(int i=1;i<=n;i++){
		int L=left(p[i-1],p[i]);
		int R=right(p[i-1],p[i]);
		dp[0][p[i]]=min({
				dp[0][p[i-1]]+L*x,
				dp[0][p[i-1]]+R*y,
				dp[1][p[i-1]]+L*y+z,
				dp[1][p[i-1]]+R*x+z
		});
		dp[1][p[i]]=min({
				dp[1][p[i-1]]+L*y,
				dp[1][p[i-1]]+R*x,
				dp[0][p[i-1]]+L*x+z,
				dp[0][p[i-1]]+R*y+z,
		});
		bit.add(p[i],-1);
	}
	printf("%lld\n",min(dp[0][p[n]],dp[1][p[n]]));
}
signed main(){
#ifdef USE_FILE_IO
	freopen("code.in","r",stdin);
	cerr<<"[File IO]"<<endl;
#endif
	int t=1;
//	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}