bzoj2131 免费的馅饼

这是$[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; } ```