bzoj2131 免费的馅饼

2018-10-09 16:11:42


这是 $[NOI1998]$ 免费馅饼的加强版

原题只需要一个暴力 $dp$

$f[i][j]$ 表示时刻 $i$ 在位置 $j$ 的最大收益

用相邻两个位置进行转移就好了


考虑换个角度思考

如果接到馅饼 $j$ 之后能够接到馅饼 $i$

那么需要满足条件: $t[i]>t[j]$ 且 $|p[i]-p[j]|<=2\times(t[i]-t[j])$

第二个式子可以看成:

$2\times(t[i]-t[j])>=p[i]-p[j]$ 且 $2\times(t[i]-t[j])>=p[j]-p[i]$

移项,得到

$2\times t[i]+p[i]>=2\times t[j]+p[j]$

$2\times t[i]-p[i]>=2\times t[j]-p[j]$

这样可以转化为一个 $(2t+p,2t-p)$ 的坐标系

一个点的 $f$ 值可以由它左下方的点转移而来

离散化之后用树状数组维护一下

复杂度 $O(nlogn)$

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
const int N=1e5+5;
struct node
{
    int tim,pos,val,x,y;
    inline friend bool operator < (node a,node b)
    {
        return a.x==b.x?a.y>b.y:a.x<b.x;
    }
}a[N];
int n,W,f[N],c[N],t[N],cnt,ans;
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline int lowbit(int x){return x&(-x);}
inline void modify(int x,int k){for (;x<=cnt;x+=lowbit(x)) c[x]=max(c[x],k);}
inline int query(int x,int res=0){for (;x;x-=lowbit(x)) res=max(res,c[x]); return res;}
int main()
{
    W=read(),n=read();
    a[0].x=a[0].y=a[0].tim=t[0]=-W;
    for (reg int i=1;i<=n;i++)
    {
        a[i].tim=read()<<1,a[i].pos=read(),a[i].val=read();
        a[i].x=a[i].tim+a[i].pos;
        t[i]=a[i].y=a[i].tim-a[i].pos;
    }
    sort(a,a+n+1); sort(t,t+n+1);
    cnt=unique(t,t+n+1)-t-1;
    for (reg int i=0;i<=n;i++) a[i].y=lower_bound(t+1,t+cnt+1,a[i].y)-t;
    for (reg int i=1;i<=n;i++)
    {
        f[i]=a[i].val+query(a[i].y);
        modify(a[i].y,f[i]); ans=max(ans,f[i]);
    }
    printf("%d\n",ans);
    return 0;
}