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