Description：

一个 $n\times n$ 的网格图，有 $m$ 个鼹鼠会依次冒出来，给出每个鼹鼠冒出来的时间 $t$ (按顺序给出)，位置 $(x,y)$ ，有一个机器人，最开始的位置任意，问最多能打几个鼹鼠。

$1\le m\le 10000$

Solution：

设 $f[i]$ 表示最后一个打 $i$ 最多能打几个，转移为 $\begin{align}f[i]=\max_{j=1}^{i-1}(f[j]+1)(|x[i]-x[j]|+|y[i]-y[j]|\le t[i]-t[j])\end{align}$ ，然而这样 $O(M^2)$ 不能通过，考虑 $DP$ 剪枝，记一个 $\begin{align}mx[i]=\max_{j=1}^{i}f[j]\end{align}$ ，那么 $mx[i]$ 单调递增在枚举 $j$ 时倒序循环，遇到 $mx[j]+1\le f[i]$ 就 $break$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int n,m;

#define MAXM 10010

struct mole

{

	int x,y,t;

}s[MAXM];

int f[MAXM];

int mx[MAXM];

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d",&s[i].t,&s[i].x,&s[i].y);

		f[i] = 1;

		for(int j = i - 1;j >= 1;--j)

		{

			if(mx[j] + 1 <= f[i])break;

			if(abs(s[i].x - s[j].x) + abs(s[i].y - s[j].y) <= s[i].t - s[j].t)

			{

				f[i] = max(f[i],f[j] + 1);

			}

		}

		mx[i] = max(mx[i - 1],f[i]);

	}

	int ans = 0;

	for(int i = 1;i <= m;++i)

	{

		ans = max(ans,f[i]);

	}

	cout << ans << endl;

	return 0;

}