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

ZBH_799 · 2025-08-20 16:51:22 · 题解

题目分析

因为我们只有两只手，所以对于一对相同元素 a_j,a_i(j<i)，想要使它们配对中间就不能拿两张及以上的牌，否则就会把 a_j 挤出左手。这样，我们就可以 DP 了。令 p_i 表示整数 i 第一次出现的位置，dp_i 表示前 i 张牌能获得的最大得分。我们可以考虑以下转移：

• 如果我们不拿第 i 张牌，则 dp_i=dp_i-1。
• 如果我们拿第 i 张牌，且在 p_i 和 i 之间不拿任何牌，则 dp_i=dp_{p_i}+v_{a_i}。
• 如果我们拿 i 张牌，且在 p_i 和 i 之间拿一张牌，则 dp_i=\max_{p_{a_j}<p_{a_i}<j<i}{(dp_{p_{a_j}}+v_{a_j}+v_{a_i})}。

但是，这样做的时间复杂的为 O(n^2)，如何优化呢？前两个转移显然不需要优化，重点来看第三个转移。注意到 p_{a_j}<p_{a_i}<j，即 \forall p_{a_i} \in (p_{a_j},p_{a_i})，dp_i 都能从 dp_{p_{a_j}} 转移过来，因此我们可以维护一棵区间修改，求单点最大值的线段树来进行优化。

AC code

#include<bits/stdc++.h>
using namespace std;
#define all(vec) vec.begin(),vec.end()
#define fr first
#define sc second
#define pq priority_queue
#define gr greater
#define lc(x) x<<1
#define rc(x) x<<1|1
using ll=long long;
using db=double;
using i128=__int128;
using pii=pair<int,int>;

const int N=4e5+5;
int n,a[2*N],b[N],pos[N];
ll dp[2*N];

namespace SGT{
    struct node{
        int l,r;
        ll tag,ma;
    }bt[8*N];

    void pushup(int x){bt[x].ma=max(bt[lc(x)].ma,bt[rc(x)].ma);}

    void pushdown(int x){
        if(bt[x].tag!=-1){
            bt[lc(x)].ma=max(bt[lc(x)].ma,bt[x].tag),bt[lc(x)].tag=max(bt[lc(x)].tag,bt[x].tag);
            bt[rc(x)].ma=max(bt[rc(x)].ma,bt[x].tag),bt[rc(x)].tag=max(bt[rc(x)].tag,bt[x].tag);
        }
        bt[x].tag=-1;
    }

    void build(int x,int l,int r){
        bt[x].l=l,bt[x].r=r,bt[x].tag=-1;
        if(l==r) return;
        int mid=(l+r)>>1;
        build(lc(x),l,mid);
        build(rc(x),mid+1,r);
        pushup(x);
    }

    void modify(int x,int l,int r,ll v){
        if(bt[x].l>=l&&bt[x].r<=r){
            bt[x].tag=max(bt[x].tag,v),bt[x].ma=max(bt[x].ma,v);
            return;
        }
        pushdown(x);
        int mid=(bt[x].l+bt[x].r)>>1;
        if(l<=mid) modify(lc(x),l,r,v);
        if(r>mid) modify(rc(x),l,r,v);
        pushup(x);
    }

    ll query(int x,int p){
        if(bt[x].l==p&&bt[x].r==p) return bt[x].ma;
        pushdown(x);
        int mid=(bt[x].l+bt[x].r)>>1;
        if(p<=mid) return query(lc(x),p);
        else return query(rc(x),p);
    }
}

void solve(){
    cin>>n;
    for(int i=1;i<=2*n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];

    SGT::build(1,1,2*n);
    for(int i=1;i<=2*n;i++){
        dp[i]=dp[i-1];
        if(pos[a[i]]){
            dp[i]=max(dp[i],dp[pos[a[i]]]+b[a[i]]);
            dp[i]=max(dp[i],SGT::query(1,pos[a[i]])+b[a[i]]);
            SGT::modify(1,pos[a[i]],i,dp[pos[a[i]]]+b[a[i]]);
        }
        pos[a[i]]=i;
    }

    cout<<dp[2*n]<<'\n';
}

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