[HNOI2004] 打鼹鼠

发表于 | 分类于 >
字数统计 : 408   |   阅读时长 ≈ 2 mins.

题目

链接

[HNOI2004]打鼹鼠

题意简述

在一个 的网格中。你可以控制一个机器人来打 只鼹鼠，如果 时刻鼹鼠和机器人处于同一网格的话，那么这个鼹鼠就会被机器人打死。而机器人每一时刻只能向相邻的网格移动一格或停留在原地不动。

机器人不能走出整个 的网格。可以自由选定机器人的初始位置。

求在这一段时间内打死尽可能多的鼹鼠的数目。

思路

DP

可以发现机器人能移动的坐标差只与时间有关。
设 $f[i]$ 为 $i$ 时刻能打死几只鼹鼠。
状态转移方程：

时间复杂度： $(n^{2})$ 。

代码

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
#define REG register
#define IN inline
#define For(x,y,z) for (REG int (x) = (y); (x) <= (z); ++(x))
#define FOR(x,y,z) for (REG int (x) = (y); (x) <  (z); ++(x))
const int kmax_num = 1e4 + 10, kmax_int = 2147483647, kmod = 1e4;

#define pii std::pair<int, int>
#define pipii std::pair<int, pii>
#define mp std::make_pair

int n, m;
pipii t[kmax_num];
int f[kmax_num];

int main()  {
    std::cin >> n >> m;
    REG int tim, x, y;
    FOR(i,0,m)  {
        std::cin >>tim >> x >> y;
        t[i] = mp(tim, mp(x, y));
    }
    
    REG int ans = 0;
    FOR(i,0,m)  {
        f[i] = 1;
        FOR(h,0,i) {
            if(t[i].first - t[h].first >= abs(t[i].second.first - t[h].second.first) +
                                          abs(t[i].second.second - t[h].second.second))
                f[i] = std::max(f[i], f[h] + 1);
        }
        ans = std::max(ans, f[i]);
    }
    printf("%d\n", ans);
    return 0;
}

杂项

  • 这里还是用了 $std::pair$ ，$std::pair$ 大法好！（虽然没什么用