[HNOI2004] 打鼹鼠

形式化题目

在一个 $n \times n$ 的网格上按时间顺序出现 $m$ 个事件, 第 $i$ 个事件是 $(t_i, x_i, y_i)$ , 表示第 $t_i$ 个时刻格子 $(x_i, y_i)$ 处出现一只鼹鼠. $t$ 不降, 同一时刻同一格子至多一只.

一个机器人在每个时刻可以停在原地或移动到相邻格子. 初始位置在时刻 1 之前可以任意选定. 若某时刻机器人所在的格子正好有鼹鼠, 那只鼹鼠就被打死.

求能打死的鼹鼠数的最大值. $m \leqslant 10^4$ .

样例

样例是 2 2 的网格, 两个事件: $(1, 1, 1)$ 和 $(2, 2, 2)$ .

从 $(1,1)$ 到 $(2,2)$ 的曼哈顿距离是 $|2-1| + |2-1| = 2$ , 而时间差只有 $2 - 1 = 1$ . 所以赶不上, 只能打死其中一只. 答案为 $1$ .

暴力解法

思路

先把"某个方案能不能全部打死"这件事写对. 一个方案就是选定的一个下标子集, 把它按时间顺序列出来后, 检查相邻两只是否赶得上.

于是最直接的做法是枚举所有子集: 用 01 序列递归, 第 $i$ 层决定第 $i$ 只打还是不打, 到叶子( $dep = m + 1$ )时按顺序检查一遍相邻可达性, 合法就更新答案.

它完全按定义结算, 不依赖任何还没证明的结论, 因此可以作为小数据对拍的基准.

代码

cpp

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-26 13:50
 * update_at: 2026-10-26 16:36
 */
// brute.cpp：小数据暴力解，用 01 序列递归枚举"这只鼹鼠打不打"，到叶子统一检查是否都赶得上。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXM = 25;

ll n, m;
ll t[MAXM], x[MAXM], y[MAXM]; // 第 i 只鼹鼠的时刻与位置
int chosen[MAXM];             // chosen[i] = 1 表示去打第 i 只，0 表示放弃
ll best;

// 检查当前选出的鼹鼠序列是否可行：相邻两只之间的曼哈顿距离不超过时间差。
bool check() {
    ll last = -1;
    for (ll i = 1; i <= m; i++) {
        if (chosen[i] == 0) {
            continue;
        }
        if (last != -1) {
            ll td = t[i] - t[last];
            ll dist = llabs(x[i] - x[last]) + llabs(y[i] - y[last]);
            if (dist > td) {
                return false;
            }
        }
        last = i;
    }
    return true;
}

ll count_chosen() {
    ll cnt = 0;
    for (ll i = 1; i <= m; i++) {
        cnt += chosen[i];
    }
    return cnt;
}

// 第 dep 层决定第 dep 只鼹鼠打不打。
void dfs(int dep) {
    if (dep == m + 1) {
        if (check()) {
            ll cnt = count_chosen();
            if (cnt > best) {
                best = cnt;
            }
        }
        return;
    }
    chosen[dep] = 0;
    dfs(dep + 1);
    chosen[dep] = 1;
    dfs(dep + 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (ll i = 1; i <= m; i++) {
        cin >> t[i] >> x[i] >> y[i];
    }

    best = 0;
    dfs(1);
    cout << best << '\n';
    return 0;
}

复杂度

枚举 $2^m$ 个子集, 每个子集检查一次 $O(m)$ . 时间 $O(m 2^m)$ , 空间 $O(m)$ 递归深度. 只有 $m \leqslant 20$ 量级可用, 而题目要求 $m \leqslant 10^4$ .

瓶颈

瓶颈是把"打不打的顺序"当成独立选择来枚举. 但合法性只约束相邻两只之间的可达性: 中间跳过了哪些鼹鼠完全不影响判定.

也就是说, 一次合法的击杀过程本质上是一条链. 既然是链, 就可以用 "以某一只结尾的最优链有多长"这个状态把它压缩掉, 不必枚举整条链.

正解

关键观察

先回答"两只鼹鼠之间能不能赶上". 设 $t_j \leqslant t_i$ , 则

\text{能赶上} \iff |x_i - x_j| + |y_i - y_j| \leqslant t_i - t_j

必要性: 每个时刻最多移动一格, $t_i - t_j$ 个时刻最多走 $t_i - t_j$ 步, 步数不会少于曼哈顿距离.
充分性: 网格里没有阻挡, 沿最短折线路径一步步走过去, 恰好用曼哈顿距离个时刻, 剩下的时间原地等待即可.

下面的图表示这个条件: 以出发格为中心、曼哈顿半径 $t_i - t_j$ 的菱形, 就是时间够用的所有格子.

text

1
2
3
4
5
6
7
8
9
10 t_j 时刻出发
 ●
 ◇ │ ◇
 ◇ │ ◇
 ◇ │ ◇
 ────────────●──────────── ← 落在菱形内即可达
 ◇ │ ◇
 ◇ │ ◇
 ◇ │ ◇
 ●

菱形内部(含边界)的点满足曼哈顿距离 $\leqslant$ 时间差. 注意是 $\leqslant$ 而不是 $<$ : 刚好用完所有时间也来得及.

于是整个问题变成在事件序列上求最长链, 其中 $j \to i$ 有边当且仅当 $j < i$ 且上述条件成立. 因为 $t$ 不降, $j < i$ 时一定有 $t_j \leqslant t_i$ , 不会形成环, 这是一个 DAG.

思路

令 $dp_i$ 表示以第 $i$ 只鼹鼠作为最后一只时, 最多能打死的只数. 转移枚举前驱:

dp_i = 1 + \max\big\{ dp_j : j < i,\ |x_i - x_j| + |y_i - y_j| \leqslant t_i - t_j \big\}

三个地方需要确认:

为什么按输入顺序扫就是拓扑序. 题目已经保证 $t$ 不降, 所以 $j < i$ 蕴含 $t_j \leqslant t_i$ . 边只从时间早的指向时间不早的, 扫到 $i$ 时它所有前驱都已算完.
为什么初值是 1. 游戏开始时初始位置自由, 机器人可以直接站在任意格子, 所以任何一只都可以作为链的开头, 不需要虚构一个起点或额外加边.
为什么不用考虑中间没打的鼹鼠. 一条链只约束相邻两项, 中间的时间与位置都是自由的; 若某只没打的鼹鼠恰好顺路, 那它本来就该被加进链里, 那是由更长的链来表达的.

答案取 $\max_i dp_i$ .

正确性可以由两条夹逼说明:

若 $dp_i = dp_j + 1$ 且 $j$ 赶得到 $i$ , 由归纳存在以 $j$ 结尾的可行方案, 接上 $i$ 即得长度 $dp_i$ 的可行方案.
任意一条可行方案 $i_1, \dots, i_k$ , 对 $s$ 归纳可证 $dp_{i_s} \geqslant s$ : $s = 1$ 时初值保证; $s > 1$ 时 $i_{s-1}$ 与 $i_s$ 相邻且 $i_{s-1} < i_s$ , 转移时枚举到它给出 $dp_{i_s} \geqslant dp_{i_{s-1}} + 1 \geqslant s$ .
于是 $k \leqslant dp_{i_k} \leqslant \max_i dp_i$ , 两个方向合起来即得最优性.

代码

main.cpp 是正式主解. main.py 是同一算法的 Python 实现, 复杂度同阶, 放在同一节.

cpp

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-26 13:50
 * update_at: 2026-10-26 16:36
 */
// main.cpp：把每只鼹鼠看成一个事件，dp[i] 表示最后打死第 i 只时的最大数目，O(m^2) 转移。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXM = 10005;

struct Mole {
    ll t; // 出现时刻
    ll x; // 行
    ll y; // 列
};

ll n, m;
Mole mole[MAXM]; // 输入的事件序列，按时间不降给出
ll dp[MAXM];     // dp[i]：以第 i 只鼹鼠作为最后一只时，最多能打死的数目

// 从第 j 只赶到第 i 只需要的时间：曼哈顿距离。机器人在 td 个时刻内可以走 td 格。
bool reachable(int j, int i) {
    ll td = mole[i].t - mole[j].t;
    ll dist = llabs(mole[i].x - mole[j].x) + llabs(mole[i].y - mole[j].y);
    return dist <= td;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (ll i = 1; i <= m; i++) {
        cin >> mole[i].t >> mole[i].x >> mole[i].y;
    }

    ll ans = 1;
    for (ll i = 1; i <= m; i++) {
        // 初始位置可以自由选择，所以每只鼹鼠都能被当作第一只。
        dp[i] = 1;
        for (ll j = 1; j < i; j++) {
            if (reachable(j, i) && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
            }
        }
        if (dp[i] > ans) {
            ans = dp[i];
        }
    }

    cout << ans << '\n';
    return 0;
}

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-26 14:05
# update_at: 2026-10-26 14:25

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    _n = next(data)
    m = next(data)

    ts = [0] * m  # 出现时刻
    xs = [0] * m  # 行
    ys = [0] * m  # 列
    for i in range(m):
        ts[i] = next(data)
        xs[i] = next(data)
        ys[i] = next(data)

    dp = [0] * m               # dp[i]：以第 i 只鼹鼠作为最后一只时最多打死的数目
    buckets = [[] for _ in range(m + 1)]  # buckets[d]：dp 值等于 d 的那些下标
    ans = 1

    for i in range(m):
        ti = ts[i]
        xi = xs[i]
        yi = ys[i]
        best = 1  # 初始位置自由，第 i 只总能被当作第一只
        # 按 dp 从大到小找第一个赶得上的前驱：它就是最优前驱，于是可以立刻停手
        for d in range(ans, 0, -1):
            found = False
            for j in buckets[d]:
                if abs(xi - xs[j]) + abs(yi - ys[j]) <= ti - ts[j]:
                    best = d + 1
                    found = True
                    break
            if found:
                break
        dp[i] = best
        buckets[best].append(i)
        if best > ans:
            ans = best

    print(ans)


if __name__ == "__main__":
    solve()

main.py 有一处常数优化: 把已知的前驱按 $dp$ 值分桶, 按 $d$ 从大到小找第一个可达的桶, 一命中就停手. 第一个命中的 $d$ 就是最大的可行 $d$ , 所以结果不变. 这样避免了 Python 里 O(m^2) 全量扫描的开销, 但复杂度上界仍是 $O(m^2)$ .

复杂度

时间 $O(m^2)$ : 内层枚举前驱, 每次常数次整数运算. $m = 10^4$ 时约 $5 \times 10^7$ 次比较.
空间 $O(m)$ : 存事件和 $dp$ , 不需要 $O(n^2)$ 的网格.

总结

本题有两个转折点.

第一是把几何条件算清楚: 从一只到另一只能不能赶上, 只取决于曼哈顿距离与时间差的大小关系, 与中间发生过什么无关.

第二是认出这是 DAG 最长路. 既然 $t$ 不降, 按输入顺序扫就是拓扑序, 于是"选哪些鼹鼠"这种看起来是指数级的组合问题, 变成了 $O(m^2)$ 的线性 DP.

同样的思路可以迁移到很多"按时间推进、需要判断两点之间来不来得及"的问题, 例如有截止时间的任务链、按时间窗排序的区间选取.

目录

形式化题目

样例

暴力解法

思路

代码

复杂度

瓶颈

正解

关键观察

思路

代码

复杂度

总结