中文题目，问你最后能最多够得到多少价值的馅饼。因为宽度10^8且个数为10^5。所以不可以用dp[x][y]表示某时间某地点的最大权值。
假设你在x点处接到饼后想去y点接饼。那么需要满足的条件是t[y]-t[x]>= | d[x]-d[y] | ，距离带绝对值，因为可以y在左x在右也可以反过来。
变化可得： ⑴t[y]-t[x]>= d[x]-d[y] ——> t[y]+d[y]>= t[x]+d[x]
⑵t[y]-t[x]>= d[y]-d[x] ——> t[y]-d[y]>= t[x]-d[x]
我们把t[x]+d[x]设为a[x].x 把t[x]-d[x]设为a[x].y 只要满足t[x].x<=t[y].x且t[x].y<=t[y].y 那么便满足条件。
我们按照先.x后.y的顺序排序。这样从左到右遍历的时候就可以保证前面的.x小于后面的.x了，之后只要考虑.y的关系
我们用数组b来存.y的值，之后去重。从1到n遍历数组a，对遍历到的a[i].y在b数组中用二分找到他对应的位置。然后去树状数组里面查找比这个数小的数中值最大的那个状态，那个状态加上a[i].v（排序后第i个的价值）就是当前i点的最大价值，再把这个值加入到树状数组里面去。在最后，直接在b数组中查找最大的编号，就可以找到总价值最大的状态，也就是答案。
#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
int b[],l;
struct dd
{
int x,y,v;
}a[];
int c[];
int add(int x,int v)
{
while(x<=l)
{
c[x]=max(c[x],v);
x+=(x&-x);
}
}
int find(int x)
{
int ans=;
while(x)
{
ans=max(ans,c[x]);
x-=(x&-x);
}
return ans;
}
int cmp(dd x,dd y)
{
if(x.x==y.x) return x.y<y.y;
return x.x<y.x;
}
int main()
{
int n,m,i,p,t;
scanf("%d%d",&m,&n);
for(i=;i<=n;i++)
{
scanf("%d%d%d",&t,&p,&a[i].v);
a[i].x=p+*t;
a[i].y=*t-p;
b[i]=a[i].y;
}
sort(a+,a+n+,cmp);
sort(b+,b++n);
l=unique(b+,b++n)-b-;
for(i=;i<=n;i++)
{
int id=lower_bound(b+,b++n,a[i].y)-b;
int ans=find(id)+a[i].v;
add(id,ans);
}
cout<<find(l)<<endl;
}