[NOIP 1996 提高组] 挖地雷

题意

$N \le 20$ 个地窖，每个有若干地雷；从任意地窖出发，每次只能移动到编号更大且连通的地窖。求一条挖雷最多的路径（输出路径与总数）。

思路

直接枚举所有路径是 $O(2^N)$ 级别， $N=20$ 时不可行。先看一个可以验证想法的朴素解：

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/**
 * 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-08-04 11:10
 * update_at: 2026-08-04 11:10
 */

// brute.cpp：小数据暴力解，使用选择序列递归枚举所有挖矿路径。
// 每一层递归在选择"下一步去哪个编号更大的连通地窖"，走到底时更新最优方案。
// 只能处理小数据：所有路径数可能是指数级。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;

int n;
int a[MAXN];            // a[i]：第 i 个地窖的地雷数
int conn[MAXN][MAXN];   // conn[i][j] = 1 表示 i 到 j 有路径（i < j）

int path[MAXN];         // 当前枚举到的路径
int ans_path[MAXN];     // 最优路径
int ans_cnt;            // 最优路径长度
int ans_sum;            // 最优路径的地雷总数

// 当前路径已走到第 dep 步，位于地窖 cur，已累计 sum 个地雷
void dfs(int dep, int cur, int sum) {
    // 结算当前方案：以 cur 结尾的这条路径
    if (ans_sum < sum) {
        ans_sum = sum;
        ans_cnt = dep;
        for (int i = 1; i <= dep; i++)
            ans_path[i] = path[i];
    }

    // 选择下一步：只能去编号更大且连通的地窖
    for (int nxt = cur + 1; nxt <= n; nxt++) {
        if (conn[cur][nxt] == 1) {
            path[dep + 1] = nxt;
            dfs(dep + 1, nxt, sum + a[nxt]);
        }
    }
}

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

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 1; i < n; i++)
        for (int j = i + 1; j <= n; j++)
            cin >> conn[i][j];

    // 可以从任意地窖开始挖
    for (int start = 1; start <= n; start++) {
        path[1] = start;
        dfs(1, start, a[start]);
    }

    for (int i = 1; i <= ans_cnt; i++)
        cout << ans_path[i] << " ";
    cout << '\n' << ans_sum << '\n';

    return 0;
}

这个暴力把挖矿过程看成选择序列：每一层递归在选择"下一步去哪个编号更大的连通地窖"，走到底（无路可走）就结算当前路径并更新最优。它正确但枚举了全部路径，路径数可以是指数级。

关键观察：移动方向永远是小编号 → 大编号，所以图是 DAG，编号顺序就是拓扑序——按编号从小到大递推时，每个地窖的前驱一定已经算好，最长路不需要枚举路径本身。

定义 $f[i]$ = 挖到地窖 $i$ 结束能挖到的最大地雷数：

f[i] = a_i + \max_{j < i,\ conn[j][i]=1} f[j], \qquad f[i] \text{ 初值 } = a_i

边界 $f[i] = a_i$ 表示"从 $i$ 开始挖、不接任何前驱"，这样"可从任一处开始"也被覆盖。答案 = $\max_i f[i]$ ，并用 pre[i] 记录最优前驱，最后沿 pre 链回溯还原路径。

以样例（ $a=[10,8,4,7,6]$ ，路径 $1\!\to\!3\!\to\!4\!\to\!5$ ）走一遍转移表：

i	a[i]	边界 f[i]	可行前驱 j（conn[j][i]=1）	转移候选 f[j]+a[i]	最终 f[i]	pre[i]
1	10	10	无	—	10	0
2	8	8	1	10+8=18	18	1
3	4	4	1	10+4=14	14	1
4	7	7	1, 3	10+7=17, 14+7=21	21	3
5	6	6	3, 4	14+6=20, 21+6=27	27	4

看第 5 行：f[5] 有两个候选前驱，取较大者 27（来自 f[4]=21），所以 pre[5]=4。沿 pre 链 5→4→3→1 回溯再反转，就得到最优路径 1 3 4 5，地雷数 27，与样例一致。注意每个 f[i] 只保留"最优前驱"一个指针，路径形状在最后统一还原——这就是 DP 相对暴力的全部节省所在。

代码

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/**
 * 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-08-04 11:10
 * update_at: 2026-08-04 11:10
 */

/* P2196 [NOIP 1996 提高组] 挖地雷 */
/* DAG 最长路 DP：地窖编号天然是拓扑序，f[i] = 以 i 结尾的最大地雷数。 */

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;

int n;
int a[MAXN];                  // a[i]：第 i 个地窖的地雷数
int conn[MAXN][MAXN];         // conn[i][j] = 1 表示 i 到 j 有路径（i < j）
int f[MAXN];                  // f[i]：挖到地窖 i 结束能挖到的最大地雷数
int pre[MAXN];                // pre[i]：最优方案中地窖 i 是从哪个地窖来的（路径还原）

int rcd[MAXN];                // 最优路径（逆序存放）
int cnt;                      // 最优路径长度

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

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    // 输入只给 i -> j（i < j）的连通关系
    for (int i = 1; i < n; i++)
        for (int j = i + 1; j <= n; j++)
            cin >> conn[i][j];

    // 边界：从地窖 i 开始挖，至少能挖到 a[i] 个
    for (int i = 1; i <= n; i++)
        f[i] = a[i];

    // 编号小的在前，编号大的在后，天然是拓扑序，按编号顺序递推即可
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (conn[j][i] == 1 && f[i] < f[j] + a[i]) {
                f[i] = f[j] + a[i];
                pre[i] = j;   // 记录最优前驱，用于路径还原
            }
        }
    }

    // 答案 = 所有 f[i] 的最大值，并记录终点下标
    int ans = 0, idx = 1;
    for (int i = 1; i <= n; i++) {
        if (ans < f[i]) {
            idx = i;
            ans = f[i];
        }
    }

    // 从终点沿 pre 链回溯，得到逆序路径
    for (int i = idx; i != 0; i = pre[i])
        rcd[++cnt] = i;

    // 逆序输出还原为正序
    for (int i = cnt; i >= 1; i--)
        cout << rcd[i] << " ";
    cout << '\n' << ans << '\n';

    return 0;
}

复杂度

递推枚举所有点对： $O(N^2)$ 时间；f[]、pre[]、conn[][] 共 $O(N^2)$ 空间。 $N \le 20$ ，绰绰有余。

总结

图上最长路只要有拓扑序就能线性递推：本题的拓扑序就是编号本身。输出方案的老套路是 pre[] 记录前驱、终点回溯、反转输出。

[NOIP 1996 提高组] 挖地雷

目录

题意

思路

代码

复杂度

总结