[HNOI2004] 打鼹鼠

怕不是鼹鼠打我

题目大意：

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

在一个 $n \times n$ 的网格中，在某些时刻鼹鼠会在某一个网格探出头来透透气。

如果 ii 时刻鼹鼠在某个网格中出现，而机器人也处于同一网格的话，那么这个鼹鼠就会被机器人打死。而机器人每一时刻只能够移动一格或停留在原地不动。机器人的移动是指从当前所处的网格移向相邻的网格，即从坐标为 $(i,j)$ 的网格移向 $(i−1,j),(i+1,j),(i,j−1),(i,j+1)$ 四个网格，机器人不能走出整个 $n \times n$ 的网格。

现在知道在一段时间内，鼹鼠出现的时间和地点，机器人在这一段时间内打死最多多少的鼹鼠。

思路：

为了方便，建立一个结构体来存储每只大耗子的信息：

struct /*好听的名字*/
{
  //时间
  //出现的 x, y 坐标
};

由于这个网格是二维的，没办法建立一维序列模型，所以没法 $O(n \space log \space n)$ 解决，所以……

$n^2$ DP，启动！！！

那么怎么去 DP 呢？

既然是 $n^2$ DP，两层循环肯定少不了：

for(int i=0;i<m;++i)
  for(int j=0;j<m;++j)

在最坏情况下，我仍然可以刚好降落在一只鼹鼠头上。所以在循环前，我们先把 DP 用的数组（$f$）全部初始化为 1：

fill(f,f+m,1);

问题来了，我们该怎样计算他够不够跑呢？

曼哈顿距离！

曼哈顿距离是种使用在几何度量空间的几何学用语，用以标明两个点在标准坐标系上的绝对轴距总和。（from baidu）

在这里，它是机器人走到指定位置的最小步数

计算公式：

$$dis(x1,y1,x2,y2) = |x1-x2|+|y1-y2|$$

只需看一下曼哈顿距能不能够跑（​time[i] - time[j]） 就可以转移了。

能转移的话:

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

最后取 $f$ 中的最大值即可。

代码就不放了，讲的这么细，大家应该都能写出来。

制作不易，请点个赞！

仅剩的真代码

代码(AC)：

#include<bits/stdc++.h>
using namespace std;
struct Node{
	int x,y,time;
}a[10005];
int f[10005];
int n,m,maxn=0;
int Manhattan_Distance(int p1,int p2){//求曼哈顿距离 
	return abs(a[p1].x-a[p2].x)+abs(a[p1].y-a[p2].y); 
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++)cin>>a[i].time>>a[i].x>>a[i].y;//输入 
	for(int i=1;i<=m;i++){
		f[i]=1;
		for(int j=1;j<i;j++){//遍历所有节点： 
			if(Manhattan_Distance(i,j)<=abs(a[i].time-a[j].time)){ 
				/*
				
				时间差：abs(a[i].x-a[j].x)
				曼哈顿距离：(abs(a[i].y-a[j].y)<=abs(a[i].time-a[j].time)
				
				因为：曼哈顿距离就是需要走的步数
				所以：如果曼哈顿距离<时间差：可以走 
				
				*/
				f[i]=max(f[i],f[j]+1);//如果可以走，取最大 
			}
		}
		maxn=max(maxn,f[i]);//取最大值 
	}
	cout<<maxn;
	return 0;
}

思路：

时间差：abs(a[i].x-a[j].x)

曼哈顿距离：(abs(a[i].y-a[j].y)<=abs(a[i].time-a[j].time)

因为：曼哈顿距离就是需要走的步数

所以：如果曼哈顿距离<时间差：可以走

无注释版(AC)：

#include<bits/stdc++.h>
using namespace std;
struct Node{
	int x,y,time;
}a[10005];
int f[10005],n,m,maxn=0;
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i].time>>a[i].x>>a[i].y
		f[i]=1;
		for(int j=1;j<i;j++){
			if(abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y)<=abs(a[i].time-a[j].time)){
				f[i]=max(f[i],f[j]+1);
			}
		}
		maxn=max(maxn,f[i]);
	}cout<<maxn;
	return 0;
}

求赞！！！

看不出哪里错的检查一下自己的输入

曼哈顿距离

标明两个点在标准坐标系上的绝对轴距总和。

公式：

$$c=\left |x_{a} -x_{b} \right | +\left |y_{a} -y_{b} \right | $$

讲解

新式中文伪代码

// 引入必要的头文件
// 定义一个结构体 a 来存储鼹鼠的信息 
结构体 a { 
    // 鼹鼠出现的时间 
    整数 time; 
    // 鼹鼠出现的 x 坐标 
    整数 x; 
    // 鼹鼠出现的 y 坐标 
    整数 y; 
    // 以该鼹鼠结尾的最长捕捉序列长度，初始化为 1 
    整数 dp /*等于*/ 1; 
    // 输入的鼹鼠出现总次数 
    整数 m; 
    // 输入的总时间范围 
    整数 n; 
    // 记录最大捕捉序列长度 
    整数 cnt; 
} 
 
// 定义一个函数 manhadun 来计算两只鼹鼠之间的曼哈顿距离 
函数 manhadun(整数 zz, 整数 zzz) { 
    // 计算并返回两只鼹鼠之间的曼哈顿距离 
    返回 绝对值(a[zz].x - a[zzz].x) + 绝对值(a[zz].y - a[zzz].y); 
} 

主函数 { 
    // 输入
    输入 a[0].n 和 a[0].m; 
 
    // 循环读取每只鼹鼠的信息 
    对于 i 从 1 到 a[0].m 执行以下操作 { 
        // 从标准输入读取第 i 只鼹鼠的出现时间、x 坐标和 y 坐标 
        从标准输入读取 a[i].time、a[i].x 和 a[i].y; 
    } 
 
    // 动态规划部分，计算以每只鼹鼠结尾的最长捕捉序列长度 
    对于 i 从 1 到 a[0].m 执行以下操作 { 
        对于 j 从 1 到 i - 1 执行以下操作 { 
            // 判断第 i 只鼹鼠是否可以从第 j 只鼹鼠的位置在规定时间内到达 
            如果 (a[i].time - a[j].time >= manhadun(i, j)) { 
                // 如果可以到达，更新以第 i 只鼹鼠结尾的最长捕捉序列长度 
                a[i].dp = 最大值(a[i].dp, a[j].dp + 1); 
            } 
        } 
        // 更新最大捕捉序列长度 
        a[0].cnt = 最大值(a[0].cnt, a[i].dp); 
    } 
 
    // 输出最大捕捉序列长度 
    输出 a[0].cnt; 

}