1427C - The Hard Work of Paparazzi(dp + 简单优化)

题意:已知有r条从西到东的街道和r条从北到南的街道,之后有n行,每一行包含t_i,x_i,y_i,t_i表示t_i秒这个人出现在(x_i,y_i)这个点,假设当前你在(x,y)点,那么你到(x_i,y_i)去接这个人需要花费abs(x-x_i)+abs(y-y_i)的时间,开始你在起点(1,1),求你最多能够接多少个人

解法:考虑dp,dp[i]表示前i个人最多能够接多少个人,之后我们进行维护一个mx[i]表示维护对于[1,i-1]个人最多能够接多少个人,之后就可以通过mx数组进行优化即可

#include<bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
#define ull unsigned long long
using namespace std;
const int maxn = 1e5 + 5;
int t[maxn],x[maxn],y[maxn];
int dp[maxn],mx[maxn];
int main(){
	int r,n;
	sc("%d%d",&r,&n);
	for(int i = 1; i <= n; i++){
		sc("%d%d%d",&t[i],&x[i],&y[i]);
		dp[i] = -1;
	}
	int ans = 0;
	x[0] = y[0] = 1;
	for(int i = 1; i <= n; i++){
		for(int j = i-1; j >= 0; j--){
			if(dp[j] >= 0 && abs(x[i]-x[j])+abs(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]);
	}
	pr("%d\n",ans);
}