CF2150C题解

· · 题解

赛时苦心研究 B 不会做，赛后发现 C 竟然比 B 简单？

（本题解一如既往地贯彻了我的废话精神？）

想了想发现自己不会贪心，所以必然有 dp 做法？

不难想到一个状态 f_{i,j} 表示 A 当前决策第 i 个物品，B 已经选了前 j 个物品时的最大价值。\ 考虑你当前这个物品 a_i，A 如果能选，说明 B 的前 j 个中没有 a_i。形式化的可以记一个 pos_i 表示 A 的第 i 个在 B 中的位置，这个限制就转化为了 pos_i>j。\ 乍一看这个 dp 应该是 O(n^3) 的，因为我们每一次都要考虑 j 的转移点，但真的是这样吗？\ 回头看一下前面推的限制，这个 j 的作用只用于约束 A 是否能选，仅此而已。所以我们从 f_{i-1,j} 能到达的有用状态只有 f_{i,j} 和 f_{i,pos_i}。

这时候就可以顺利推出这个 O(n^2) 的 dp 转移了，特别注意每一个东西至少要被其中一个人选：

f_{i, \max (j,pos_{i})}= \max (f_{i, \max (j,pos_{i})},f_{i-1,j})\\ f_{i,j}= \max (f_{i,j},(f_{i-1,j}+w_{a_{i}})\times [pos_i>j] )

code。然后就可以获得一发罚时的好成绩。

考虑优化，这个东西看起来就很有前途，因为发现转移就是按 pos_i 的大小分成两部分，第一维又可以滚掉，就和这个很像。

f_{j}=f_{j}+w_{a_i},j<pos_i\\ f_{pos_i}=\max\{f_{pos_i},\max_{j<pos_i}\{f_j\}\}

此时只需要上一个维护区间最大值的线段树即可，第二种转移在主函数取一次 \max。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200010;
int w[N],a[N],b[N],c[N],pos[N];
struct node{
    int l,r,data,lazy;
}p[4*N];
void build(int pos,int l,int r){
    p[pos].l=l,p[pos].r=r,p[pos].lazy=0,p[pos].data=0;
    if(l==r) return ;
    int mid=(l+r)/2;
    build(pos*2,l,mid);build(pos*2+1,mid+1,r);
}
void pd(int pos){
    int v=p[pos].lazy;p[pos].lazy=0;
    p[pos*2].data+=v,p[pos*2+1].data+=v;
    p[pos*2].lazy+=v,p[pos*2+1].lazy+=v;
}
void update(int pos,int l,int r,int v){
    if(p[pos].l==l&&p[pos].r==r){
        p[pos].lazy+=v;
        p[pos].data+=v;
        return ;
    }
    if(p[pos].lazy) pd(pos);
    int mid=(p[pos].l+p[pos].r)/2;
    if(l<=mid) update(pos*2,l,min(r,mid),v);
    if(r>mid) update(pos*2+1,max(mid+1,l),r,v);
    p[pos].data=max(p[pos*2].data,p[pos*2+1].data);
}
int query(int pos,int l,int r){
    if(p[pos].l==l&&p[pos].r==r) return p[pos].data;
    if(p[pos].lazy) pd(pos);
    int mid=(p[pos].l+p[pos].r)/2,ans=-1e14;
    if(l<=mid) ans=max(ans,query(pos*2,l,min(r,mid)));
    if(r>mid) ans=max(ans,query(pos*2+1,max(mid+1,l),r));
    return ans;
}
void solve(){
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>w[i];
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i],c[b[i]]=i;
    for(int i=1;i<=n;i++) pos[i]=c[a[i]];
    build(1,0,n);
    for(int i=1;i<=n;i++){
        int now=query(1,0,pos[i]-1),res=query(1,pos[i],pos[i]);
        if(res<now) update(1,pos[i],pos[i],now-res);
        update(1,0,pos[i]-1,w[a[i]]);
        //if(pos[i]>j) f[i][j]=max(f[i][j],f[i-1][j]+w[a[i]]);
        //f[i][max(j,pos[i])]=max(f[i][max(j,pos[i])],f[i-1][j]);
    }
    int ans=query(1,0,n);
    cout<<ans<<'\n';
}

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