前言

~~怎么会有人做得出第五题做不出第四题啊！~~

题意

题目传送门

分析

最开始看到五个操作的时候，差点以为是大模拟，险些把我劝退，还好读懂题目之后，发现这题其实很像 CSP-S 2024 T3，不过本题要更复杂一些。

类似的，我们把相同的两张牌的下标转化成一个区间，手玩一下就可以发现：区间包含是不合法的，每个区间最多与另一个区间交叉。

因此，我们可以注意到：交集为空的两个区间的信息是一定可以累加的，存在包含关系的两个区间的信息是一定不可以累加的，存在交集但无包含关系的两个区间需要分类讨论。

这不是明显可以 DP 嘛！

我们可以发现，区间之间只可交叉一次的限制在于一张牌在被拿起后，若想要有贡献，最多只能再拿起一张其它牌。我们已经确认可以使用 DP，那么显然设计状态的时候多加一维即可，即：

f_{i,0}

表示

A_i

产生贡献且手上有另一张同样的牌时的最大答案。

f_{i,1}

表示

A_i

产生贡献且右手上有另一张同样的牌时的最大答案。

至于状态转移——状态都设计出来了，转移不是非常显然？不过需要注意：

操作 2 中的两张牌会同时消失，这本来会影响答案的传递，但是题目又限制了每种牌最多出现两次，所以直接把 $f_{i,1}$ 的信息存在第二张牌的位置即可。
转移时需要求前缀最大值，这个可以线性转移有点困难，因为 $f_{i,0}$ 需要存在第一张牌的位置以排除包含情况的答案贡献。本题也比较特殊，可以用线段树也可以用树状数组，下面的代码用的是树状数组。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
/*
	f[i][0]：第一张牌正在手上 
	f[i][1]：第一张牌正在右手上 
*/
const int N=1e6+5;
int n,a[N],la[N],now[N];
long long v[N],f[N][2],t1[N],t2[N];
void add1(int x,long long v){
	for(;x<=n;x+=x&-x){
		t1[x]=max(t1[x],v);
	}
}
long long ask1(int x){
	long long ans=0;
	for(;x;x-=x&-x){
		ans=max(ans,t1[x]);
	}
	return ans;
}
void add2(int x,long long v){
	for(;x<=n;x+=x&-x){
		t2[x]=max(t2[x],v);
	}
}
long long ask2(int x){
	long long ans=0;
	for(;x;x-=x&-x){
		ans=max(ans,t2[x]);
	}
	return ans;
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
//	freopen("tx.in","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<=(n<<1);i++){
		scanf("%d",&a[i]);
		la[i]=now[a[i]];
		now[a[i]]=i;
	}
	for(int i=1;i<=n;i++) scanf("%lld",&v[i]);
	n<<=1;
	for(int i=1;i<=n;i++){
		if(!la[i]) continue;
		f[i][0]=max(ask1(la[i]),ask2(la[i]))+v[a[i]];
		f[i][1]=ask1(la[i])+v[a[i]];
		add1(i,f[i][0]);
		add2(la[i],f[i][1]);
	}
	printf("%lld\n",ask1(n));
	return 0;
}

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

文章操作

前言

题意

分析

代码

相关推荐

评论

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