Cf1427c the hard work of paparazzi

CF1427C The Hard Work of Paparazzi

The question ： There is one r*r(r≤500) The map of , The starting position is (1,1), Yes n(n≤1e5) An individual will appear at a certain point at a certain time ( Give... In ascending order of time ), Ask how many people you can meet at most .

solution ： The idea of this problem is very novel , I always thought about bfs, But I can't write it out , because n It's too big . I didn't expect it to be linear at all dp . At first I heard that the solution to this problem was dp When , It feels like n ^ 2 The cycle of （dp[i] On behalf of i At a time , How many people can you meet up front ）, But it will obviously time out , Here is a feature to be found , If it is n ^ 2 The kind of cycle , Will find r It's useless , In fact, it is to use r To optimize the second cycle . First , The distance between two points is at most 2r, And the time is strictly ascending , that i It must be from [0,i-2r] Turn around , The biggest must be in [i-4r,i-2r] Between （ I think the reason should be that the values here are updated from the previous values , So it can be reduced to this range ）, But for the [i-2r,i-1] This part needs to be judged （ The following code also determines [i-4r,i-2r] Of ）. In this case ,n ^ 2 The complexity can be optimized to n * r, It's a bit like yesterday's topic .

Thank you for pointing out ~

Code ：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5+10;
int dp[N];
struct xx {
    
	int t, x, y;
}a[N];
int dis(xx a1, xx a2) {
    
	return abs(a1.x-a2.x)+abs(a1.y-a2.y);
}
int main() {
    
	memset(dp, -1, sizeof dp);
	int r, n;
	scanf("%d%d", &r, &n);
	a[0].x = 1, a[0].y = 1; dp[0] = 0;
	for(int i = 1; i <= n; ++i) scanf("%d%d%d", &a[i].t, &a[i].x, &a[i].y);
	for(int i = 1; i <= n; ++i) {
    
		for(int j = max(0, i-1-r*4); j < i; ++j) {
    
			if(dp[j] != -1 && a[i].t - a[j].t >= dis(a[i], a[j])) 
				dp[i] = max(dp[i], dp[j]+1);
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; ++i) ans = max(ans, dp[i]);
	printf("%d\n", ans);
	return 0;
}