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

题目分析

因为我们只有两只手，所以对于一对相同元素

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

CPP

#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;
}

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

文章操作

题目分析

AC code

相关推荐

评论

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