动态规划题
从题目中可以发现是一个时间递增的过程，所以只要是在时间晚的点都是后出现的。换句话说，在条件达成时，前面的点可以到达后面的点。
于是题目就变为了求一条满足条件的最长的链，发现非常的像LIS（最长上升子序列），只要将 f[i]>=f[j] 的条件变为 abs(x[i]-x[j])+abs(y[i]-y[j])<=t[i]-t[j] 即可
但是此题不可以用 LIS 的优化，变为 nlogn 的复杂度，因为此题的序列没有传递性。
比如 LIS 中 a,b,c 三个数 a<b,b<c 则 a<c 。但是此题没有这个规律，所以不能进行优化。
但是可以通过 break 来减少时间
定义数组 mx ， mx[i] 表示 f[1] 到 f[i] 的最大值，所以 mx[i]>=mx[i-1] ，所以第二层循环从后向前循环，如果 mx[j]+1<=f[i] 那说明之后就没有状态可以转移了，就 break 退出循环
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
int n,m,f[],x[],y[],t[],ans,mx[];
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
scanf("%d%d%d",&t[i],&x[i],&y[i]);
f[i]=;
}
mx[]=;
for(int i=;i<=m;i++){
for(int j=i-;j>=;j--){//从后向前
if(mx[j]+<=f[i]){
break;
}
if(abs(x[i]-x[j])+abs(y[i]-y[j])<=t[i]-t[j]){
f[i]=max(f[i],f[j]+);
}
}
mx[i]=max(mx[i-],f[i]);
ans=max(ans,f[i]);
}
printf("%d\n",ans);
return ;
}