Luogu

分析

这是一道DP题。
用$f[i]$来表示到第$i$只地鼠最多能打的只数。
那么对于每一个状态，都要在前面的所有地鼠中选一只，然后直接过来打这一只。
决策就直接选最大即可。
状态转移方程也就列出了：

$f[i]=max\{f[j]+1\} (|x[i]-x[j]|+|y[i]-y[j]|\leq |time[i]-time[j]|)$

然后还有边界问题。这个不难想：因为机器人可从任意地方开始，所以$f[i]=1$

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
using namespace std;
int x[10010],y[10010],t[10010],f[10010]; //f[i]表示到第i只地鼠最多能打的只数 
inline int read() //读入优化
{
    int X=0,w=1; char ch=0;
    while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
    return X*w;
}
int main()
{
    int n=read(),m=read(),ans=-1;
    for (re int i=1;i<=m;i++) t[i]=read(),x[i]=read(),y[i]=read(); //输入
    for (re int i=1;i<=m;i++) f[i]=1; //边界
    for (re int i=1;i<=m;i++) //DP
    {
        for (re int j=1;j<i;j++)
            if (abs(x[i]-x[j])+abs(y[i]-y[j])<=abs(t[i]-t[j]))
                f[i]=max(f[i],f[j]+1);
        ans=max(ans,f[i]); //更新答案
    }
    printf("%d\n",ans); //输出
    return 0;
}