题目链接

P2285 打鼹鼠

思路

很明显，这是一道$dp$题，因为标签已经告诉我们了（不是

怎么$dp$呢？

棋盘？三维必炸啊，二维本蒟蒻不会

时间？更离谱了

所以就只能从鼹鼠下手了

设$dp_i$为到第$i$只鼹鼠时最多能打到几只

因为我们要守株待兔（鼠），所以初始化$dp_i=1$

若两鼹鼠之间的曼哈顿距离小于出现时间差

此时转移方程为$dp_i=min(dp[i],dp[j]+1)$

代码

#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;
}

更新日志

2025/10/12 07:02

查看所有更新日志

• 7ced7-Reuploads previous blogs于 2025/10/12

版权所有

许可证：署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0)