第十八届西电程序设计竞赛-H

九月 06, 2020

H.美丽的建筑

题意

给出n<1e5个建筑材料

每个建筑材料有3个属性

编号，高度，美丽值

要求从中选出一些建筑材料

将他们按照编号升序排列后

他们的高度必须满足先递增后递减(只递增或只递减也可)

问选出的材料能组成最大的美丽值是多少

题解

乍一看像最长上升子序列的变形题

但实际上这里并不关心最长的高度递增递减子序列

而是在符合高度递增递减的子序列中寻找权值和最大的值

分别从两端做dp 记前缀pre[i]为1到i的最优解(最大美丽值之和)

记后缀suf[i]为n到i的最优解

以前缀为例，我们每次转移状态时

需要找到以高度x(x从1到当前高度-1之间)为结尾的最长上升子序列中最大的美丽值记为maxn

pre[i]=max(pre[i],maxn+data[i].val);

由于有1e5个零件所以以高度为线段树的区间左右端点建树,将美丽值之和作为区间最大值

每次转移询问树中(1,data[i].high-1)的区间内最大的美丽值

更新完pre[i]后，将以当前高度data[i].high为结尾的最优解 pre[i]

单点更新线段树中高度为data[i].high的点对应的最大值(美丽值)

后缀同理

最后On 取得最终答案 ans=max(pre[i]+suf[i]-data[i].val,ans); //第i个零件被计算两次

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=1e5+5;
const ll Mod=998857459;
/*

*/
class SegTree{
public:
    #define mid ((L+R)>>1)
    #define Leftson now<<1
    #define Rightson now<<1|1
    struct segtree{int L,R;ll maxn;};
    segtree tree[Max<<2];
    void push_up(int now){
        tree[now].maxn=max(tree[Leftson].maxn,tree[Rightson].maxn);
        return;
    }
    void build(int L,int R,int now=1){
        tree[now]={L,R,0};
        //cout<<L<<" "<<R<<endl;
        if(L==R)return;
        //int mid=(L+R)>>1;
        build(L,mid,Leftson);
        build(mid+1,R,Rightson);
        push_up(now);
        return;
    }
    void updata(int pos,ll val,int now=1){
        if(tree[now].L==tree[now].R){
            tree[now].maxn=max(tree[now].maxn,val);
            return;
        }
        if(pos<=tree[Leftson].R)updata(pos,val,Leftson);
        if(pos>=tree[Rightson].L)updata(pos,val,Rightson);
        push_up(now);return;
    }
    ll query(int qL,int qR,int now=1){
        if(qL>qR)return 0;
        if(tree[now].R<=qR&&tree[now].L>=qL)return tree[now].maxn;
        ll maxn=0;
        if(tree[Leftson].R>=qL)maxn=max(maxn,query(qL,qR,Leftson));
        if(tree[Rightson].L<=qR)maxn=max(maxn,query(qL,qR,Rightson));
        return maxn;
    }
}preHigh,sufHigh;
ll pre[Max],suf[Max];
struct Data{ll indx,val,high;}data[Max];
bool cmp(Data x,Data y){return x.indx<y.indx;};
int main() {
    Turnoff;
    int n;cin>>n;
    preHigh.build(1,n,1);
    sufHigh.build(1,n,1);
    for(int i=1;i<=n;i++){
        ll indx,val,high;
        cin>>indx>>val>>high;
        data[i]={indx,val,high};
    }
    sort(data+1,data+1+n,cmp);
    for(int i=1;i<=n;i++){
        pre[i]=max(pre[i],preHigh.query(1,data[i].high-1,1)+data[i].val);
        //cout<<"ok"<<endl;
        preHigh.updata(data[i].high,pre[i],1);
    }
    for(int i=n;i>=1;i--){
        suf[i]=max(suf[i],sufHigh.query(1,data[i].high-1,1)+data[i].val);
        sufHigh.updata(data[i].high,suf[i],1);
    }
    ll ans=0;
    for(int i=1;i<=n;i++)ans=max(ans,pre[i]+suf[i]-data[i].val);
    cout<<ans<<endl;
}

查看评论