算法1

直接暴力线性DP，感觉是1e8的复杂度，结果过了

时间复杂度 m*m

参考文献

C++ 代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 10010;

struct Rat{
    int x, y, t;
    bool operator<(const Rat& another) const
    {
        return t < another.t;
    }
}rats[N];

int f[N];

int n, m;

int get_dist(int i, int j)
{
    return abs(rats[i].x - rats[j].x) + abs(rats[i].y - rats[j].y);
}

int main()
{
    scanf("%d %d", &n, &m);   
    for(int i = 0; i < m; ++ i)
    {
        int t, x, y;
        scanf("%d %d %d", &t, &x, &y);
        rats[i] = {x, y, t};
    }
    sort(rats, rats + m);
    for(int i = 0; i < m; ++ i) f[i] = 1;
    for(int i = 0; i < m; ++ i)
        for(int j = i + 1; j < m; ++ j)
            if(get_dist(i, j) <= rats[j].t - rats[i].t)
                f[j] = max(f[j], f[i] + 1);
    int res = 0;
    for(int i = 0; i < m; ++ i) res = max(res, f[i]);
    printf("%d", res);
    return 0;
}