题解 P7302 [NOI1998] 免费的馅饼

Push_Y · 2021-04-06 23:23:58 · 题解

这是一道经典的数据结构优化dp

思路

定义 f_i 表示接住第 i 个馅饼

对于 f_i ，考虑从 j∈[1,i) 的 f_j 转移得到

这里的 j 满足 abs(p_i-p_j)≤2(t_i-t_j)，于是接下来的问题是如何维护每个 i 对应的 j 的集合了。于是将 j 的条件式展开，得到

此时按第一个式子排序，再用树状数组维护另一个式子。这样做可以使两条式子同时都满足，于是 pi 与 p_j 的大小关系便无关紧要了。

树状数组维护过程

因为两条式子不等号方向不同，其他题解的做法

这样的话两次排序就都升序就解决了。

当然，也可以像我一样把第一条式子降序排序

具体实现细节

按第一个式子排序后用树状数组维护第二个式子，这里由于数值大，对第二个式子离散化。

CODE

#include <bits/stdc++.h>
#define int long long
using namespace std;

inline int gin(){
    char c=getchar();
    int s=0,f=1;
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        s=(s<<3)+(s<<1)+(c^48);
        c=getchar();
    }
    return s*f;
}

const int N=1e5+5;
int b[N],w,n,k,c[N];

struct node{
    int t,p,v,l,r;
}a[N];
bool cmpl(node x,node y){\\第一条式子降序排序
    return x.l>y.l;
}
bool cmpr(node x,node y){
    return x.r<y.r;
}

void update(int x,int val){
    while(x<=k){
        c[x]=max(c[x],val);
        x+=x&-x;
    }
}

int query(int x){
    int res=0;
    while(x){
        res=max(res,c[x]);
        x-=x&-x;
    }
    return res;
}

signed main(){
    w=gin(),n=gin();
    for(int i=1;i<=n;i++){
        a[i].t=gin(),a[i].p=gin(),a[i].v=gin();
        a[i].l=a[i].p-2*a[i].t;//存第一条式子
        a[i].r=b[i]=a[i].p+2*a[i].t;//存第二条式子
    }

   \\离散化                        
    sort(a+1,a+n+1,cmpr);
    sort(b+1,b+n+1);
    k=unique(b+1,b+n+1)-b;
    for(int i=1;i<=n;i++)
        a[i].r=lower_bound(b+1,b+n+1,a[i].r)-b;

    sort(a+1,a+n+1,cmpl);
    for(int i=1;i<=n;i++){
        int tmp=query(a[i].r);
        update(a[i].r,tmp+a[i].v);//对于刚转移得到的dp值tmp，加入到树状数组里
    }
    printf("%lld\n",query(k));
    return 0;
}