HNOI2004.打鼹鼠

题目

P2285 [HNOI2004] 打鼹鼠

算法标签: 动态规划

思路

显然这个是一个动态规划的问题, 最朴素的想法就是$f[t][i][j]$表示当前时间是$t$并且机器人的位置是$[i,j]$的击杀鼹鼠的最大值, 但是观察数据范围, 无论是时间或者空间都会超, 需要考虑时间复杂度更低的做法
设$f[i]$表示当前击杀了第$i$只鼹鼠的所有方案中击杀数量最多的方案, 可以由前一个状态进行转移, 但是要求所有鼹鼠按照时间从小到大进行排序

代码

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int M = 1e4 + 10;int n, m;
struct Node {int t, x, y;bool operator< (const Node &n) const {return t < n.t;}
} w[M];
int f[M];bool check(const Node &n1, const Node &n2) {return abs(n1.t - n2.t) >= abs(n1.x - n2.x) + abs(n1.y - n2.y);
}int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> m;for (int i = 1; i <= m; ++i) {int t, x, y;cin >> t >> x >> y;w[i] = {t, x, y};f[i] = 1;}sort(w + 1, w + m + 1);int ans = 1;for (int i = 1; i <= m; ++i) {for (int j = 1; j < i; ++j) {if (check(w[i], w[j])) f[i] = max(f[i], f[j] + 1);}ans = max(ans, f[i]);}cout << ans << "\n";return 0;
}