线性DP—洛—打鼹鼠

发布时间：2026/7/17 21:48:55

P2285 [HNOI2004] 打鼹鼠

题目描述

鼹鼠是一种很喜欢挖洞的动物，但每过一定的时间，它还是喜欢把头探出到地面上来透透气的。

根据这个特点阿牛编写了一个打鼹鼠的游戏：在一个 \(n \times n\) 的网格中，在某些时刻鼹鼠会在某一个网格探出头来透透气。

你可以控制一个机器人来打鼹鼠，如果 \(i\) 时刻鼹鼠在某个网格中出现，而机器人也处于同一网格的话，那么这个鼹鼠就会被机器人打死。

而机器人每一时刻只能够移动一格或停留在原地不动。机器人的移动是指从当前所处的网格移向相邻的网格，即从坐标为 \((i, j)\) 的网格移向 \((i-1, j), (i+1, j), (i, j-1), (i, j+1)\) 四个网格，机器人不能走出整个 \(n \times n\) 的网格。

游戏开始时，你可以自由选定机器人的初始位置。

现在知道在一段时间内，鼹鼠出现的时间和地点，请编写一个程序使机器人在这一段时间内打死尽可能多的鼹鼠。

输入格式

第一行为 \(n, m\ (1 \le n \le 10^3, 1 \le m \le 10^4)\)，其中 \(m\) 表示在这一段时间内出现的鼹鼠的个数。

接下来的 \(m\) 行中每行有三个数据 \(t, x, y\ (1 \le t \le 2.5 \times 10^7, 1 \le x,y \le n)\)，表示在游戏开始后 \(t\) 个时刻，在第 \(x\) 行第 \(y\) 个网格里出现了一只鼹鼠。

\(t\) 按不降的顺序给出。

注意同一时刻可能出现多只鼹鼠，但同一时刻同一地点只可能出现一只鼹鼠。

输出格式

仅包含一个非负整数，表示被打死鼹鼠的最大数目。

输入输出样例 #1

输入 #1

2 2
1 1 1
2 2 2

输出 #1

刚开始想法

错误转移状态代码：

点击查看代码

for(int i = 1;i <= m;i++)
{int temp = 0;for(int j = 1;j < i;j++){int dis1 = a[i].t-a[j].t;    //a数组存了鼹鼠出现的时间和坐标int dis2 = abs(a[i].x-a[j].x) + abs(a[i].y-a[j].y);if(dis1 >= dis2 && dis1%2 == dis2%2){temp = max(temp,dp[a[j].x][a[j].y]);}}dp[a[i].x][a[i].y] = max(temp+1,dp[a[i].x][a[i].y]);  ans = max(ans, dp[a[i].x][a[i].y]);
}

一开始认为是网格dp，但由于网格数据大，鼹鼠数多，后想到只枚举出现的鼹鼠，跟新相应网格的dp。一开始没看题，机器人可以不动，认为要加时间距离和曼哈顿距离奇偶性相同的条件。而且我想网格最大dp值的时间是最新跟新的时间，因为我的内层是时间从小到大，每次只需要看最近的时间即可。这样前面每个鼹鼠时间信息无法保存，导致所有同一点鼹鼠不同时间却共享一个最大dp值。我前面小的时间点也是最大的dp值，会跟新最大值temp,但其实这个网格最大dp是后面的时间跟新来的，而后面的时间可能太大，时间距离小小于曼哈顿距离可能无法跟新当前时间dp值。
至于为什么一开始认为思路没问题，就是老想着自己的状态转移方程没错，但是这个同一位置相应小时间对应的dp值错了没想到。

正确做法

有数据范围，想到遍历鼹鼠信息进行dp是对的，但不该是网格dp，而是线性dp，dp[i]表示遍历第i只鼹鼠的最大值。我的时间，坐标信息在结构体里保存的都有，完全没必要用二维来存坐标信息反而忽略了时间信息。
正确代码：

点击查看代码

#include <bits/stdc++.h>
using namespace std;
struct ty
{int t,x,y;
}a[10010];
int dp[10010];        //第i只鼹鼠最大值
int n,m,ans;
int main()
{cin>>n>>m;for(int i = 1;i <= m;i++) {int t,x,y;cin>>t>>x>>y;a[i] = {t,x,y};dp[i] = 1;    //赋初值，机器人第一步任意达到}for(int i = 1;i <= m;i++){int temp = 0;for(int j = 1;j < i;j++){int dis1 = a[i].t-a[j].t;int dis2 = abs(a[i].x-a[j].x) + abs(a[i].y-a[j].y);if(dis1 >= dis2){temp = max(temp,dp[j]);}}dp[i] = temp+1;  ans = max(ans, dp[i]);}cout<<ans;return 0;
}