第一行为 n,m(n≤1000,m≤104),其中 m 表示在这一段时间内出现的鼹鼠的个数,接下来的 m 行中每行有三个数据 time,x,y 表示在游戏开始后 time 个时刻,在第 x 行第 y 个网格里出现了一只鼹鼠。time 按递增的顺序给出。注意同一时刻可能出现多只鼹鼠,但同一时刻同一地点只可能出现一只鼹鼠。
#include<bits/stdc++.h> usingnamespace std; using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t; using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;
structEvent { int t, x, y; };
int32_tmain(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<Event> a(m + 1); vector<int> f(m + 1, 1); for (int i = 1; i <= m; i++) cin >> a[i].t >> a[i].x >> a[i].y; int ans = 0; for (int i = 1; i <= m; i++) { for (int j = 1; j < i; j++) { int dist = abs(a[i].x - a[j].x) + abs(a[i].y - a[j].y); if (dist <= a[i].t - a[j].t) f[i] = max(f[i], f[j] + 1); } ans = max(ans, f[i]); } cout << ans << '\n'; return0; }
总结与常见问题
常见问题
为什么状态定义成“最后打到第 i 只”? 只有知道最后所在的位置和时刻,才能判断下一只鼹鼠是否来得及赶到。