[CF2150C] Limited Edition Shop 题解

你说的对，但是我为什么要求 Bob。

不妨将

v,a,b

变换，使得

a=[1,2,\ldots,n]

。研究 Bob 能选出哪些数。注意到若 Bob 先跳过了一个下标

x

，然后选择了一个下标

y<x

，这一定是不合法的，因为跳过

x

实质上是让 Alice 不断选直到选

x

，期间一定会选到

y

。对于 Bob，这个限制拍到二维平面上就是一个被选点左上方区域内所有点也必须选。

然后这个东西正着 dp 是难以优化的，考虑从右向左 dp，

f_{i,j}

表示考虑到

i

，当前最严格的限制是

j

，即之后

b_x\ge j

的都要选，此时 Bob 能得到的最小价值。则有三种转移。

$f_{i,j}\to f_{i-1,j}(b_i<j)$ ，表示不选 $b_i$ 。
$f_{i,j}+b_i\to f_{i-1,b_i}(b_i<j)$ ，表示选 $b_i$ 。
$f_{i,j}+b_i\to f_{i-1,j}(b_i>j)$ ，表示不得不选 $b_i$ 。

显然

f_{i}\to f_{i-1}

时的修改形如一个区间和一个单点，于是可以使用线段树维护。

code

CPP

#include<bits/stdc++.h>
#define pb emplace_back
#define pob pop_back
using namespace std;
typedef long long ll;
const ll maxn=200007,ee=1e18;
ll n,a[maxn],p[maxn],tp[maxn],f[maxn],sum,tmp[maxn];
struct Tree{
	ll val[maxn<<2],add[maxn<<2];
	void clear(ll n){for(ll i=1;i<=4*n;i++) val[i]=ee,add[i]=0;}
	void pushup(ll rt){val[rt]=min(val[rt<<1],val[rt<<1|1]);}
	void pushdown(ll rt){
		if(!add[rt]) return;
		val[rt<<1]+=add[rt],val[rt<<1|1]+=add[rt];
		add[rt<<1]+=add[rt],add[rt<<1|1]+=add[rt],add[rt]=0;
	}
	void upd(ll l,ll r,ll x,ll y,ll z,ll rt){
		if(x<=l&&r<=y) return val[rt]+=z,add[rt]+=z,void();
		pushdown(rt); ll mid=(l+r)>>1;
		if(x<=mid) upd(l,mid,x,y,z,rt<<1);
		if(mid<y) upd(mid+1,r,x,y,z,rt<<1|1);
		pushup(rt);
	}
	void modify(ll l,ll r,ll x,ll z,ll rt){
		if(l==r) return val[rt]=z,void();
		pushdown(rt); ll mid=(l+r)>>1;
		if(x<=mid) modify(l,mid,x,z,rt<<1);
		else modify(mid+1,r,x,z,rt<<1|1);
		pushup(rt);
	}
	ll qry(ll l,ll r,ll x,ll y,ll rt){
		if(r<x||l>y) return ee;
		if(x<=l&&r<=y) return val[rt];
		pushdown(rt); ll mid=(l+r)>>1;
		return min(qry(l,mid,x,y,rt<<1),qry(mid+1,r,x,y,rt<<1|1));
	}
}tree;
int main(void){
	//freopen("data.in","r",stdin);
	//freopen("data.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	ll T=1; cin>>T;
	for(;T--;){
		cin>>n,sum=0;
		for(ll i=1;i<=n;i++) cin>>a[i],sum+=a[i];
		for(ll i=1;i<=n;i++) cin>>tp[i];
		for(ll i=1;i<=n;i++) cin>>p[i];
		for(ll i=1;i<=n;i++) tmp[i]=a[tp[i]];
		for(ll i=1;i<=n;i++) a[i]=tmp[i];
		for(ll i=1;i<=n;i++) tmp[tp[i]]=i;
		for(ll i=1;i<=n;i++) p[i]=tmp[p[i]];
		tree.clear(n+1),tree.modify(1,n+1,n+1,0,1);
		for(ll i=n;i>=1;i--){
			tree.modify(1,n+1,p[i],tree.qry(1,n+1,p[i]+1,n+1,1),1);
			tree.upd(1,n+1,1,p[i],a[p[i]],1);
		}
		cout<<sum-tree.val[1]<<"\n";
	}
	return 0;
}

[CF2150C] Limited Edition Shop 题解

文章操作

相关推荐

评论

[CF2150C] Limited Edition Shop 题解