题意
给定 \(n\) 个点 \((x_i,y_i)\) 和对应时间 \(time_i\)，求从任意点开始，每单位时间静止或四向移动，在 \(time_i\) 时停留的点数的最大值，保证 \(time_i\) 顺序输入
sol
线性 dp
记 \(f_i\) 表示停留在第 \(i\) 个点时，点数的最大值，则转移方程为
注意数组初始化全为 \(1\)
代码
#include <iostream>
#include <algorithm>
#include <cstring>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
typedef pair<int, PII> PIP;
const int N = 10005;
int n, m;
int f[N];
PIP g[N];
int dist(PII a, PII b){
return abs(a.x - b.x) + abs(a.y - b.y);
}
int main(){
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i ++ ) scanf("%d%d%d", &g[i].x, &g[i].y.x, &g[i].y.y);
int ans = 1;
for (int i = 1; i <= m; i ++ ) f[i] = 1;
for (int i = 2; i <= m; i ++ )
for (int j = 1; j < i; j ++ )
if (dist(g[i].y, g[j].y) <= g[i].x - g[j].x) f[i] = max(f[i], f[j] + 1), ans = max(ans, f[i]);
printf("%d\n", ans);
return 0;
}