专栏文章

CF2150C题解

FForgive_Me
CF2150C题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@minrk7g0
此快照首次捕获于
2025/12/02 07:11
3 个月前
此快照最后确认于
2025/12/02 07:11
3 个月前
查看原文
赛时苦心研究 B 不会做，赛后发现 C 竟然比 B 简单？
（本题解一如既往地贯彻了我的废话精神？）
想了想发现自己不会贪心，所以必然有 dp 做法？
不难想到一个状态 fi,jf_{i,j} 表示 AA 当前决策第 ii 个物品，BB 已经选了前 jj 个物品时的最大价值。
考虑你当前这个物品 aia_i，AA 如果能选，说明 BB 的前 jj 个中没有 aia_i。形式化的可以记一个 posipos_i 表示 AA 的第 ii 个在 BB 中的位置，这个限制就转化为了 posi>jpos_i>j。
乍一看这个 dp 应该是 O(n3)O(n^3) 的，因为我们每一次都要考虑 jj 的转移点，但真的是这样吗？
回头看一下前面推的限制，这个 jj 的作用只用于约束 AA 是否能选，仅此而已。所以我们从 fi−1,jf_{i-1,j} 能到达的有用状态只有 fi,jf_{i,j} 和 fi,posif_{i,pos_i}。
这时候就可以顺利推出这个 O(n2)O(n^2) 的 dp 转移了，特别注意每一个东西至少要被其中一个人选：
fi,max⁡(j,posi)=max⁡(fi,max⁡(j,posi),fi−1,j)fi,j=max⁡(fi,j,(fi−1,j+wai)×[posi>j])f_{i, \max (j,pos_{i})}= \max (f_{i, \max (j,pos_{i})},f_{i-1,j})\\ f_{i,j}= \max (f_{i,j},(f_{i-1,j}+w_{a_{i}})\times [pos_i>j] )
code。然后就可以获得一发罚时的好成绩。
考虑优化，这个东西看起来就很有前途，因为发现转移就是按 posipos_i 的大小分成两部分，第一维又可以滚掉，就和这个很像。
fj=fj+wai,j<posifposi=max⁡{fposi,max⁡j<posi{fj}}f_{j}=f_{j}+w_{a_i},j<pos_i\\ f_{pos_i}=\max\{f_{pos_i},\max_{j<pos_i}\{f_j\}\}
此时只需要上一个维护区间最大值的线段树即可，第二种转移在主函数取一次 max⁡\max。
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200010;
int w[N],a[N],b[N],c[N],pos[N];
struct node{
	int l,r,data,lazy;
}p[4*N];
void build(int pos,int l,int r){
	p[pos].l=l,p[pos].r=r,p[pos].lazy=0,p[pos].data=0;
	if(l==r) return ;
	int mid=(l+r)/2;
	build(pos*2,l,mid);build(pos*2+1,mid+1,r);
}
void pd(int pos){
	int v=p[pos].lazy;p[pos].lazy=0;
	p[pos*2].data+=v,p[pos*2+1].data+=v;
	p[pos*2].lazy+=v,p[pos*2+1].lazy+=v;
}
void update(int pos,int l,int r,int v){
	if(p[pos].l==l&&p[pos].r==r){
		p[pos].lazy+=v;
		p[pos].data+=v;
		return ;
	}
	if(p[pos].lazy) pd(pos);
	int mid=(p[pos].l+p[pos].r)/2;
	if(l<=mid) update(pos*2,l,min(r,mid),v);
	if(r>mid) update(pos*2+1,max(mid+1,l),r,v);
	p[pos].data=max(p[pos*2].data,p[pos*2+1].data);
}
int query(int pos,int l,int r){
	if(p[pos].l==l&&p[pos].r==r) return p[pos].data;
	if(p[pos].lazy) pd(pos);
	int mid=(p[pos].l+p[pos].r)/2,ans=-1e14;
	if(l<=mid) ans=max(ans,query(pos*2,l,min(r,mid)));
	if(r>mid) ans=max(ans,query(pos*2+1,max(mid+1,l),r));
	return ans;
}
void solve(){
	int n;cin>>n;
	for(int i=1;i<=n;i++) cin>>w[i];
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i],c[b[i]]=i;
	for(int i=1;i<=n;i++) pos[i]=c[a[i]];
	build(1,0,n);
	for(int i=1;i<=n;i++){
		int now=query(1,0,pos[i]-1),res=query(1,pos[i],pos[i]);
		if(res<now) update(1,pos[i],pos[i],now-res);
		update(1,0,pos[i]-1,w[a[i]]);
		//if(pos[i]>j) f[i][j]=max(f[i][j],f[i-1][j]+w[a[i]]);
		//f[i][max(j,pos[i])]=max(f[i][max(j,pos[i])],f[i-1][j]);
	}
	int ans=query(1,0,n);
	cout<<ans<<'\n';
}

signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int T;cin>>T;while(T--) solve();
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...