[HNOI2004]打鼹鼠
题目链接：[洛谷P2285][https://www.luogu.com.cn/problem/P2285]
题目大意：给出 n*n 的网格，每个鼹鼠有一个出现时间，你每次可以移动一步，问最多能打死多少。
input
第一行为n（n<=1000）, m（m<=10000），其中m表示在这一段时间内出现的鼹鼠的个数，接下来的m行中每行有三个数据time,x,y表示有一只鼹鼠在游戏开始后time个时刻，在第x行第y个网格里出现了一只鼹鼠。Time按递增的顺序给出。注意同一时刻可能出现多只鼹鼠，但同一时刻同一地点只可能出现一只鼹鼠。
Sample input
2 2
1 1 1
2 2 2
Sample output
1
思路
起始位置是可以自由挑选的，肯定挑一个一上来就能打死鼹鼠的地方。
dp[i] 表示前i只鼹鼠最多能打死多少。
拿样例举个栗子，我们一上来就打死第一只鼹鼠。第二只鼹鼠在1秒后出现，我们从（1，1）走到（2，2）的时间是1+1=2秒（就是横坐标之差加上纵坐标之差，矩形可以平移）
此时 t2 - t1 < dis，没法打死第二只。
把样例改一下，第二只鼹鼠在第三秒出现。现在就来得及打死第二只。
此时 dp[ 2 ] = dp[ 1 ] + 1。
对于鼹鼠更多的情况也是一样的，其实很简单，代码也好写。
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 10100;
int dp[maxn], ans;
struct node{//鼹鼠出现的时间，坐标
int time, x, y;
}e[maxn];
int main(){
int n, m; scanf("%d%d", &n, &m);
for(int i=1; i<=m; i++) scanf("%d%d%d", &e[i].time, &e[i].x, &e[i].y);
for(int i=1; i<=m; i++){//打到第几只鼹鼠了
int time_i = e[i].time, xi = e[i].x, yi = e[i].y;
for(int j=1; j<i; j++){//在打死当前这只鼹鼠前，是从哪只鼹鼠过来的
int time_j = e[j].time, xj = e[j].x, yj = e[j].y;
if(time_i - time_j >= abs(xi-xj) + abs(yi-yj)) dp[i] = max(dp[i], dp[j] + 1);//可以到达当前的这只鼹鼠
}
}
for(int i=1;i<=m;i++) ans=max(ans,dp[i]);
printf("%d
", ans+1);
return 0;
}