打鼹鼠
题目链接
思路
很明显，这是一道题，因为标签已经告诉我们了（不是
怎么呢？
棋盘？三维必炸啊，二维本蒟蒻不会
时间？更离谱了
所以就只能从鼹鼠下手了
设为到第只鼹鼠时最多能打到几只
因为我们要守株待兔（鼠），所以初始化
若两鼹鼠之间的曼哈顿距离小于出现时间差
此时转移方程为
代码
#include<cstdio>
#include<cmath>
#define fo(i,x,y) for(register int i=x;i<=y;++i)
#define go(i,x,y) for(register int i=x;i>=y;--i)
#define INF 0x3f3f3f3f
#define il inline
#define ll long long
#define ull unsigned long long
using namespace std;
const int N = 1005, M = 10005;
int n, m, dp[M], ans;
struct NODE {
int time, x, y;
}node[M];
il int max(const int &a, const int &b) {return a > b ? a : b;}
int main() {
scanf("%d%d", &n, &m);
fo(i, 1, m) scanf("%d%d%d", &node[i].time, &node[i].x, &node[i].y), dp[i] = 1;
fo(i, 1, m) {
fo(j, 1, i - 1) {
if(abs(node[i].x - node[j].x) + abs(node[i].y - node[j].y) <= abs(node[i].time - node[j].time)) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
fo(i, 1, m) ans = max(ans, dp[i]);
printf("%d\n", ans);
return 0;
}