自动搬运

查看原文

来自洛谷，原作者为

	SIXIANG32 废物

搬运于2025-08-24 21:35:57，当前版本为作者最后更新于2021-03-11 20:01:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题好像是我 19 年在 ** 机构试听的时候给做的题。woc 我当时连红题都切不稳让我做蓝
现在再看这道题刚开始我只想到了三维状态，看到题解的一维状态恍然大悟 Orz 各路神仙先。
闲话少说，切入正题——

首先这道题我们显然会想到 $f_{t,x,y}$ 表示在 $t$ 这个时间节点中身处 $(x,y)$ 这个地方最多能打多少鼹鼠。
然后我们四连通填表就好惹，但是，这个空间开不下去呀/fad

所以我们要另寻捷径。我们换一种思路，设 $f_p$ 为抓鼹鼠序列以 $p$ 结尾时我们最多能抓多少小鼠。

当我们确定好了状态之后，这道题已经完成了一大半了。我们先枚举 $p$ 作为起点（毕竟起点任意，能抓就抓），那么考虑转移，显然我们可以枚举一个 $i$ 为下一个我们要抓的鼹鼠。

那么怎么判定能抓呢？我们记录不了路径啊，可是由于起点任意，所以我们可以假装在这个鼹鼠的位置，拓展我们又假装在那个鼹鼠的位置。也就是说，我们可以直接枚举一个 $i$ 作为下一个要抓的鼹鼠。

怎么判断能不能抓到呢？我们只要算一算他们的曼哈顿距离（$\left| (x_0-x_1)\right|+\left| (y_0 - y_1)\right|$）能不能够跑（$val_p-val_i$） 就可以转移了。

转移方程是什么呢？不难写出来是 $f_p = \max(f_p, f_i + 1)$。

如何初始化呢？因为我们枚举的 $p$ 作为起点可以抓所以 $f_p = 1$。

最后的答案可能不一定是 $f_m$，因为不一定这就是最大的，要从头到尾在枚举一遍才行。

上代码：

#include <iostream> 
#include <cmath>
#define MAXN 100000
using namespace std;
struct node {
	int x, y, val;
}in[MAXN + 10];
int n, m, f[MAXN + 10], ans = 0;
int max(int x, int y) {return ((x > y) ? (x) : (y));}
int dist(int x, int y, int xx, int yy) {//计算曼哈顿距离
	return abs(x - xx) + abs(y - yy);
}
int main() {
	cin >> n >> m;
	for(int p = 1; p <= m; p++)
		cin >> in[p].val >> in[p].x >> in[p].y;
	for(int p = 1; p <= m; p++) {
		f[p] = 1;
		for(int i = 1; i < p; i++)
			if(dist(in[p].x, in[p].y, in[i].x, in[i].y) <= in[p].val - in[i].val)//是否可以转移
				f[p] = max(f[p], f[i] + 1);
	}	
	for(int p = 1; p <= m; p++)//求最大值
		ans = max(ans, f[p]);
	cout << ans << endl;
}