C. The Hard Work of Paparazzi （DP)

C. The Hard Work of Paparazzi （DP)

令$dp[i]$表示前$i$个地点能获得的最大答案。
$mx[i]$表示$dp[j],j\in [1,i]$的最大值，该数组用来优化时间。
考虑状态转移：显然如果两者距离小于等于时间差即可。
$dp[i]=max(dp[i],dp[j]+1)$。

时间复杂度：$O(nr)$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define il inline
int r,n,x[N],y[N],t[N],dp[N],mx[N];
int ans;
int main(){
	scanf("%d%d",&r,&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&t[i],&x[i],&y[i]);
		dp[i]=-1;
	}
	x[0]=y[0]=1;
	for(int i=1;i<=n;i++){
		for(int j=i-1;~j;j--){
			if(dp[j]>=0&&abs(x[i]-x[j])+abs(y[i]-y[j])<=t[i]-t[j]){
				dp[i]=max(dp[i],dp[j]+1);
			}
			if(dp[i]>=mx[j]+1) break;
		}
		ans=max(ans,dp[i]),mx[i]=max(mx[i-1],dp[i]);
	}
	printf("%d\n",ans);
	return 0;
}

或者不用$mx[]$数组，直接第二维优化到$4r$。
因为最大时间差可以围一圈，显然用$4r$内的状态进行转移即可，前面的状态已经包括在$4r$里了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define il inline
int r,n,x[N],y[N],t[N],dp[N];
int ans;
int main(){
	scanf("%d%d",&r,&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&t[i],&x[i],&y[i]);
		dp[i]=-1;
	}
	x[0]=y[0]=1;
	for(int i=1;i<=n;i++){
		for(int j=i-1;j>=max(0,i-4*r);j--){
			if(dp[j]>=0&&abs(x[i]-x[j])+abs(y[i]-y[j])<=t[i]-t[j]){
				dp[i]=max(dp[i],dp[j]+1);
			}
			//if(dp[i]>=mx[j]+1) break;
		}
		ans=max(ans,dp[i]);//,mx[i]=max(mx[i-1],dp[i]);
	}
	printf("%d\n",ans);
	return 0;
}