BZOJ-2131: 免费的馅饼

Description

1<=w,t[i]<=10^8,1<=n<=100000。

显然dp。通过馅饼来更新馅饼。
然而看一看可以通过j更新i的条件：
|p[i]-p[j]|<=2*(t[i]-t[j]) t[i]>t[j]
转化一下： 2*t[i]-p[i]>=2*t[j]-p[j] 2*t[i]+p[i]>=2*t[j]+p[j] t[i]>=t[j]
发现前两个不等式可以推出第三个不等式，所以可以忽略第三个不等式，就变成了一个二维偏序问题。
排序+树状数组。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,w,ans,b[101000],c[101000],tot;
inline int getid(int x)
{
    int l=1,r=tot+1,mid;
    while(l<r)
    {
        mid=l+r>>1;
        if(x<=c[mid]) r=mid;
        else l=mid+1;
    }
    return r;
}
struct node
{
    int t,p,v;
}a[101000];
inline bool cmp(node x,node y) {return x.t==y.t?x.p>y.p:x.t<y.t;}
int f[101000];
inline void fix(int x,int y) {while(x<=tot) f[x]=max(f[x],y),x+=-x&x;}
inline int query(int x) {int re=0; while(x>0) re=max(re,f[x]),x-=-x&x; return re;}
int main()
{
    scanf("%d%d",&w,&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d%d",&a[i].t,&a[i].p,&a[i].v);
        int x=a[i].t*2+a[i].p,y=a[i].t*2-a[i].p;
        b[i]=a[i].p=x; a[i].t=y;
    }
    sort(b+1,b+n+1); c[++tot]=b[1];
    for(int i=2;i<=n;++i) if(b[i]!=b[i-1]) c[++tot]=b[i];
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;++i)
    {
        int tmp=query(getid(a[i].p));
        tmp+=a[i].v; fix(getid(a[i].p),tmp);
        ans=max(ans,tmp);
    }
    printf("%d",ans);
    return 0;
}