P2196 [NOIP 1996 提高组] 挖地雷

发表于

P2196 [NOIP 1996 提高组] 挖地雷

题目描述

在一个地图上有 $N\ (N \le 20)$ 个地窖，每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后每次可以移动到一个编号比当前节点大且联通的节点去挖地雷，当无满足条件的节点时挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。

输入格式

有若干行。

第 $1$ 行只有一个数字，表示地窖的个数 $N$。

第 $2$ 行有 $N$ 个数，分别表示每个地窖中的地雷个数。

第 $3$ 行至第 $N+1$ 行表示地窖之间的连接情况：

第 $3$ 行有 $n-1$ 个数（$0$ 或 $1$），表示第一个地窖至第 $2$ 个、第 $3$ 个 $\dots$ 第 $n$ 个地窖有否路径连接。如第 $3$ 行为 $1\space 1\space 0\space 0\space 0\cdots 0$，则表示第 $1$ 个地窖至第 $2$ 个地窖有路径，至第 $3$ 个地窖有路径，至第 $4$ 个地窖、第 $5$ 个 $\dots$ 第 $n$ 个地窖没有路径。

第 $4$ 行有 $n-2$ 个数，表示第二个地窖至第 $3$ 个、第 $4$ 个 $\dots$ 第 $n$ 个地窖有否路径连接。

……

第 $n+1$ 行有 $1$ 个数，表示第 $n-1$ 个地窖至第 $n$ 个地窖有否路径连接。（为 $0$ 表示没有路径，为 $1$ 表示有路径）。

输出格式

第一行表示挖得最多地雷时的挖地雷的顺序，各地窖序号间以一个空格分隔，不得有多余的空格。

第二行只有一个数，表示能挖到的最多地雷数。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
5
10 8 4 7 6
1 1 1 0
0 0 0
1 1
1

输出 #1

1
2
1 3 4 5
27

说明/提示

【样例解释】
最优路径为 $1 \to 3 \to 4 \to 5$，结果为 $27$。

【题目来源】
NOIP 1996 提高组第三题。

思路分析 + 代码实现

地窖之间依据编号（从小到大）构成一个 DAG ，相当于一个在有向无环图（DAG）上求最长路径的问题，每个节点有正权值（地雷数）。所以一开始想到的是拓扑排序，用 BFS 解决，代码如下：

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
#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 25;
vector<int> G[MAXN];
int a[MAXN];
struct State{
    int u, cnt;
    vector<int> rec;
};
int main(){
    int N, ans = 0;
    cin >> N;
    for(int i = 1; i <= N; i++)
        cin >> a[i];
    for(int t, i = 1; i < N; i++)
        for(int j = i + 1; j <= N; j++) {
            cin >> t;
            if (t) G[i].push_back(j);
        }
    vector<int> ans_rec;
    queue<State> Q;
    for(int i = 1; i <= N; i++) {
        State t = {i, a[i]};
        t.rec.push_back(i);
        Q.push(t);
    }
    while (!Q.empty()) {
        State now = Q.front();
        Q.pop();
        if (now.cnt > ans) {
            ans = now.cnt;
            ans_rec.clear();
            ans_rec = now.rec;
        }
        for(int v : G[now.u]) {
            State t = now;
            t.u = v;
            t.rec.push_back(v);
            t.cnt += a[v];
            Q.push(t);
        }
    }
    for(int i : ans_rec)
        cout << i << " ";
    cout << "\n" << ans;
    return 0;
}

当然也可以用记忆化搜索，时间复杂度 $O(n^2)$ ，代码如下：

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
#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 25;
bool connected[MAXN][MAXN];
int a[MAXN], dp[MAXN], N;
int dfs(int x) {
    if (dp[x]) return dp[x];
    int t = 0;
    for(int i = x + 1; i <= N; i++)
        if (connected[x][i])
            t = max(t, dfs(i));
    return dp[x] = a[x] + t;
}
int main() {
    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 >> connected[i][j];
    int ans = 0;
    for(int i = 1; i <= N; i++)
        ans = max(ans, dfs(i));
    for(int i = 1; i <= N; i++)
        if (dp[i] == ans) {
            cout << i << " ";
            for(int j = i + 1; j <= N; j++)
                if (connected[i][j] && dp[i] == a[i] + dp[j])
                    cout << (i = j) << " "; // 输出与赋值合并
        }
    cout << "\n" << ans;
    return 0;
}

注意根据答案推路径的细节。

当然， DP 更加简洁，设 $dp[i]$ 表示以地窖 $i$ 为起点能挖到的最大地雷数。

对于每个地窖 $i$，考虑它所有能到达的后续节点 $j$（满足 $j > i$ 且 $connected[i][j] = 1$）则状态转移方程为：

DP 部分代码如下（其他与 DFS 做法相同）：

1
2
3
4
5
6
7
for(int i = N; i >= 1; i--) {
    dp[i] = a[i];
    for(int j = N; j > i; j--)
        if (connected[i][j])
            dp[i] = max(dp[i], a[i] + dp[j]);
    ans = max(ans, dp[i]);
}