题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=2131
思路： 题目给出了每个馅饼的下落时间t，和位置p,以及价值v，我们可以得到如下状态转移方程：
dp[i] = max(dp[j]) + v[i] (|p[j] - p[i]| <= 2*|t[i] - t[j]|)
我们将约束条件拆开来：p[i] - p[j] <= 2*t[i]-2*t[j]&&p[i] - p[j] <= 2*t[j] - 2*t[i]
上面式子移向后可得： 2*t[j] - p[j] <= 2*t[i] - p[i]&&2*t[j] + p[j] <= 2*t[i] + p[i];
我们可以用 a[i].x = p[i] + 2*t[i];
a[i].y = 2*t[i] - p[i];
式子就变成了： a[j].x <= a[i].x&&a[j].y <= a[i].y；
对于点i来说，他的上一个状态点j必须满足上面的式子的约束，对于点i我们需要得到所有满足条件的点j的最大值。
其实这个式子就是一个二维偏序，二维偏序之前写过，只要我们对 a[i].x排序，对a[i].y建树状数组维护就好了。
实现代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int M = 1e5 + ;
int n,m,cnt,val[M],c[M],b[M];
struct node{
int x,y,val;
}a[M]; bool cmp(node a,node b){
if(a.x == b.x) return a.y < b.y;
return a.x < b.x;
} void add(int x,int p){
while(x <= cnt){
c[x] = max(c[x],p);
x += (x&-x);
}
} int getsum(int x){
int ans = ;
while(x){
ans = max(ans,c[x]);
x -= (x&-x);
}
return ans;
} int main()
{
int t,p;
cin>>m>>n;
for(int i = ;i <= n;i ++){
cin>>t>>p>>a[i].val;
a[i].x = *t + p;
a[i].y = *t - p;
b[i] = a[i].y;
}
sort(a+,a++n,cmp);
sort(b+,b++n);
cnt = unique(b+,b++n) - b-;
int ans;
for(int i = ;i <= n;i ++){
int id = lower_bound(b+,b++cnt,a[i].y)-b;
ans = getsum(id)+a[i].val;
add(id,ans);
}
cout<<getsum(cnt)<<endl;
}