P11727 [JOIG 2025] 神経衰弱 2 / Pair Matching 2 题解

线段树优化 DP。

观察可发现，海狸比太郎每次拿起一张牌，左手的牌必然会丢掉。考虑 DP，设

dp_i

为前

i

张牌的最大得分，显然

dp_i\larr dp_{i-1}

。

对于第一次出现的牌

i

，它不能加分，则必然

dp_i=dp_{i-1}

。

对于第二次出现的牌

i

，它能加分当且仅当上一次出现的牌没丢掉，也就是说自从那张牌被右手拿起后最多拿一张其他的牌。设上一次出现的这张牌位置为

o_i

。当这段时间没拿其他牌时，

dp_i\larr dp_{o_i-1}+V_{A_i}

。

如果有必要拿一张其他牌，那么它必然能加分，并且它的上一次出现在

o_i

之前（不然两张

A_i

之间超过一张牌了）。而且，这张牌的两次出现之间也不能超过一张牌，那么一定是

o_i

。所以有

dp_i\larr \max\limits_{o_j<o_i<j<i}\{dp_{o_j}+V_{A_j}+V_{A_i}\}

前两种转移都好做，最后一种线段树优化。因为转移是按照

i

递增的顺序求

dp_i

的，所以可以将前面枚举到的

o_j

对应的

j

放到小根堆里，当第一次

i>j

时，

j<i

永远都会成立，所以用

dp_{o_j}+V_{A_j}

更新区间

(o_j,j)

的

\max

。线段树上维护，最后单点查询即可。

代码

CPP

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576#include <iostream>
#include <queue>
using namespace std;
using ll= long long;
const int N=800005;
ll val[N<<2],tag[N<<2];
void app(int u,ll x) {
	val[u]=max(val[u],x);
	tag[u]=max(tag[u],x);
}
void pushup(int u) {
	val[u]=max(val[u<<1],val[u<<1|1]);
}
void pushdown(int u) {
	if(tag[u]) {
		app(u<<1,tag[u]);
		app(u<<1|1,tag[u]);
		tag[u]=0;
	}
}
void upd(int u,int l,int r,int s,int t,ll x) {
	if(s<=l&&r<=t) {
		app(u,x);
		return;
	}
	pushdown(u);
	int mid=(l+r)>>1;
	if(s<=mid) upd(u<<1,l,mid,s,t,x);
	if(t>mid) upd(u<<1|1,mid+1,r,s,t,x);
	pushup(u);
}
ll query(int u,int l,int r,int s) {
	if(l==r) return val[u];
	pushdown(u);
	int mid=(l+r)>>1;
	if(s<=mid) return query(u<<1,l,mid,s);
	else return query(u<<1|1,mid+1,r,s);
}
priority_queue<pair<int,pair<int,ll> > > pq;
int n,a[N],pos[N];
void upd(int l,int r,ll w) {
	pq.emplace(-r,make_pair(l,w));
}
void upd(int x) {
	while(pq.size()) {
		int l=pq.top().second.first,r=-pq.top().first;
		if(r>=x) return;
		upd(1,1,n+n,l,r,pq.top().second.second);
		pq.pop();
	}
}
ll v[N],dp[N],c[N],mx[N];
int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n+n;i++) {
		cin>>a[i];
		pos[a[i]]^=i;
	}
	for(int i=1;i<=n;i++)
		cin>>v[i];
	for(int i=1;i<=n+n;i++) {
		dp[i]=dp[i-1];
		int o=pos[a[i]]^i;
		upd(i);
		if(o>i) {
			if(i+1<o)
				upd(i+1,o-1,dp[i]+v[a[i]]);
			continue;
		}
		dp[i]=max(dp[i],query(1,1,n+n,o)+v[a[i]]);
		dp[i]=max(dp[i],dp[o-1]+v[a[i]]);
	}
	cout<<dp[n+n];
	return 0;
}

其实我的方法复杂了，不用堆，不要枚举

o_j

，直接枚举

j

，就肯定也有

j<i

。

P11727 [JOIG 2025] 神経衰弱 2 / Pair Matching 2 题解

文章操作

相关推荐

评论

P11727 [JOIG 2025] 神経衰弱 2 / Pair Matching 2 题解