题解 P5621 【[DBOI2019]德丽莎世界第一可爱】

· · 题解

【题意】

四维空间内有若干点，每个点有权值。

找到一些点，使得他们在每一维上都单调不降，求最大的权值和。

【分析】

把点按坐标排序后，依次枚举每个点。

在前 i-1 个点中找每一维都小于等于 p_i，并且收益最大的点，计算以 p_i 为最后一个点的最大收益。

再把 p_i 加入点集。

动态维护点集信息，可以用K-D Tree。

套路地，维护某个子树中点的边界以便于搜索时剪枝。

【算法】

K-D Tree

【代码】

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=5e4+5;
const double A=0.75;
int n;
struct point{
    int x[4];
    LL c;
    bool operator <(point b)const{
        for(int j=0;j<4;j++) if(x[j]^b.x[j]) return x[j]<b.x[j];
        return 0;
    }
    bool operator <=(point b)const{
        for(int j=0;j<4;j++) if(x[j]>b.x[j]) return 0;
        return 1;
    }
}p[maxn],a[maxn];
int D;
bool cmp(point x,point y){
    return x.x[D]<y.x[D];
}
LL now,ans;
LL max(LL x,LL y){
    return x>y?x:y;
}
LL min(LL x,LL y){
    return x<y?x:y;
}
struct KDT{
    int rt,tot;
    int rub[maxn],top;
    struct ele{
        point p;
        int l,r,s,mx[4],mi[4];
        LL c;
    }t[maxn];
    #define ls(k) t[k].l
    #define rs(k) t[k].r
    #define s(k) t[k].s
    #define p(k) t[k].p
    #define c(k) t[k].c
    #define mid (l+r>>1)
    void pushup(int k){
        s(k)=1;
        for(int i=0;i<4;i++) t[k].mx[i]=t[k].mi[i]=p(k).x[i];
        c(k)=p(k).c;
        if(ls(k)){
            for(int i=0;i<4;i++){
                t[k].mx[i]=max(t[k].mx[i],t[ls(k)].mx[i]);
                t[k].mi[i]=min(t[k].mi[i],t[ls(k)].mi[i]);
            }
            c(k)=max(c(k),c(ls(k)));
            s(k)+=s(ls(k));
        }
        if(rs(k)){
            for(int i=0;i<4;i++){
                t[k].mx[i]=max(t[k].mx[i],t[rs(k)].mx[i]);
                t[k].mi[i]=min(t[k].mi[i],t[rs(k)].mi[i]);
            }
            c(k)=max(c(k),c(rs(k)));
            s(k)+=s(rs(k));
        }
    }
    int New(){
        return top?rub[top--]:++tot;
    }
    int build(int l,int r,int d){
        if(l>r) return 0;
        int k=New();
        D=d;
        nth_element(p+l,p+mid,p+1+r,cmp);
        p(k)=p[mid];
        ls(k)=build(l,mid-1,(d+1)&3);
        rs(k)=build(mid+1,r,(d+1)&3);
        pushup(k);
        return k;
    }
    void clear(int k,int pos){
        if(ls(k)) clear(ls(k),pos);
        p[pos+s(ls(k))+1]=p(k);
        rub[++top]=k;
        if(rs(k)) clear(rs(k),pos+s(ls(k))+1);
    }
    void check(int &k,int d){
        int c=A*s(k);
        if(s(ls(k))>c||s(rs(k))>c){
            clear(k,0);
            k=build(1,s(k),d);
        }
    }
    void insert(int &k,point p,int d){
        if(!k){k=New(),ls(k)=rs(k)=0,p(k)=p,pushup(k);return;}
        if(p.x[d]<=p(k).x[d]) insert(ls(k),p,(d+1)&3);
        else insert(rs(k),p,(d+1)&3);
        pushup(k);
        check(k,d);
    }
    void query(int k,point p){
        if(!k) return;
        if(c(k)<=now) return;
        if(p(k)<=p) now=max(now,p(k).c);
        if(t[k].mx[0]<=p.x[0]&&t[k].mx[1]<=p.x[1]&&t[k].mx[2]<=p.x[2]&&t[k].mx[3]<=p.x[3]){now=max(now,c(k));return;}
        if(t[ls(k)].mi[0]<=p.x[0]&&t[ls(k)].mi[1]<=p.x[1]&&t[ls(k)].mi[2]<=p.x[2]&&t[ls(k)].mi[3]<=p.x[3]) query(ls(k),p);
        if(t[rs(k)].mi[0]<=p.x[0]&&t[rs(k)].mi[1]<=p.x[1]&&t[rs(k)].mi[2]<=p.x[2]&&t[rs(k)].mi[3]<=p.x[3]) query(rs(k),p);
    }
}T;
char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define getchar gc
int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
int main(){
    freopen("P5621.in","r",stdin);
    freopen("P5621.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++){
        for(int j=0;j<4;j++) a[i].x[j]=read();
        a[i].c=read();
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++){
        now=0;
        T.query(T.rt,a[i]);
        a[i].c+=now;
        ans=max(ans,a[i].c);
        T.insert(T.rt,a[i],0);
    }
    printf("%lld\n",ans);
    return 0;
}