Loading... # 洛谷 P2285 打鼹鼠 题解 ## 题目描述 鼹鼠是一种很喜欢挖洞的动物，但每过一定的时间，它还是喜欢把头探出到地面上来透透气的。根据这个特点阿牛编写了一个打鼹鼠的游戏：在一个 $n \times n$ 的网格中，在某些时刻鼹鼠会在某一个网格探出头来透透气。你可以控制一个机器人来打鼹鼠，如果 $i$ 时刻鼹鼠在某个网格中出现，而机器人也处于同一网格的话，那么这个鼹鼠就会被机器人打死。而机器人每一时刻只能够移动一格或停留在原地不动。机器人的移动是指从当前所处的网格移向相邻的网格，即从坐标为 $(i, j)$ 的网格移向 $(i-1, j), (i+1, j), (i, j-1), (i, j+1)$ 四个网格，机器人不能走出整个 $n \times n$ 的网格。游戏开始时，你可以自由选定机器人的初始位置。 现在知道在一段时间内，鼹鼠出现的时间和地点，请编写一个程序使机器人在这一段时间内打死尽可能多的鼹鼠。 ## 输入 第一行为 $n, m$（$n \le 1000$，$m \le {10}^4$），其中 $m$ 表示在这一段时间内出现的鼹鼠的个数，接下来的 $m$ 行中每行有三个数据 $\mathit{time}, x, y$ 表示在游戏开始后 $\mathit{time}$ 个时刻，在第 $x$ 行第 $y$ 个网格里出现了一只鼹鼠。$\mathit{time}$ 按递增的顺序给出。注意同一时刻可能出现多只鼹鼠，但同一时刻同一地点只可能出现一只鼹鼠。 ## 输出 仅包含一个正整数，表示被打死鼹鼠的最大数目。 ## 解题思路 这道题的解题思路其实很简单， 由于`time`可能很大， 因此不能模拟时间步来解题。 首先需要对所有的鼹鼠出现按时间顺序排队，设`dist[i]`为机器人在`time[i]`时间走到对应的鼹鼠出现的位置`pos[i]`时， 所能打到的鼹鼠的最大数量。 发现当$j < i$时，机器人能从`j`对应的位置转移到`i`对应的位置的条件是：两个位置之间的欧式距离小于等于时间差， 因此可以通过线性dp动态更新 ### 注意点 本体不可以使用类似`ans[N][N]`的方式存储数量， 在循环过程动态更新， 原因如下： 可能存在`j < i && k < i && j !=k`， 满足`pos[j] == pos[k] == pos[i]`， 如此， 当第一次利用`j`更新`ans`数组后， 再利用`k`更新会导致错误 ## AC代码 ```cpp #include <cstdio> #include <cstdlib> #include <iostream> #include <vector> #include <cstring> #include <algorithm> #define endl '\n' using namespace std; const int N = 1e4 + 10, M = 1e3 + 10; typedef pair<int, int> PII; int n, m; struct T { int time; int x; int y; bool operator<(const T& it) const { return time < it.time; } } rec[N]; int dist[N]; int answer = 0; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; for(int i = 1; i <= m; i ++) { int time, x, y; cin >> time >> x >> y; rec[i] = {time, x, y}; } sort(rec + 1, rec + m + 1); for(int i = 1; i <= m; i ++) { int nx = rec[i].x, ny = rec[i].y, ntime = rec[i].time; dist[i] = 1; for(int j = 1; j < i; j ++) { int x = rec[j].x, y = rec[j].y, time = rec[j].time; if(abs(nx - x) + abs(ny - y) <= ntime - time) { dist[i] = max(dist[i], dist[j] + 1); } } answer = max(answer, dist[i]); } cout << answer << endl; return 0; } ``` 最后修改：2025 年 03 月 07 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏