题解：P11727 [JOIG 2025] 神経衰弱 2 / Pair Matching 2
poembelief
·
·
题解
前言
怎么会有人做得出第五题做不出第四题啊！
题意
题目传送门
分析
最开始看到五个操作的时候，差点以为是大模拟，险些把我劝退，还好读懂题目之后，发现这题其实很像 CSP-S 2024 T3，不过本题要更复杂一些。
类似的，我们把相同的两张牌的下标转化成一个区间，手玩一下就可以发现：区间包含是不合法的，每个区间最多与另一个区间交叉。
因此，我们可以注意到：交集为空的两个区间的信息是一定可以累加的，存在包含关系的两个区间的信息是一定不可以累加的，存在交集但无包含关系的两个区间需要分类讨论。
这不是明显可以 DP 嘛！
我们可以发现，区间之间只可交叉一次的限制在于一张牌在被拿起后，若想要有贡献，最多只能再拿起一张其它牌。我们已经确认可以使用 DP，那么显然设计状态的时候多加一维即可，即：
$f_{i,1}$ 表示 $A_i$ 产生贡献且右手上有另一张同样的牌时的最大答案。
至于状态转移——状态都设计出来了，转移不是非常显然？不过需要注意：
1. 操作 2 中的两张牌会同时消失，这本来会影响答案的传递，但是题目又限制了每种牌最多出现两次，所以直接把 $f_{i,1}$ 的信息存在**第二张牌的位置**即可。
2. 转移时需要求前缀最大值，这个可以线性转移有点困难，因为 $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;
}
```