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。线段树上维护，最后单点查询即可。

:::info[代码]

#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。