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
5
10 8 4 7 6
1 1 1 0
0 0 0
1 1
1
输出 #1
1 3 4 5
27
说明/提示
【样例解释】 最优路径为 $1 \to 3 \to 4 \to 5$，结果为 $27$。
【题目来源】 NOIP 1996 提高组第三题。
思路分析 + 代码实现
地窖之间依据编号（从小到大）构成一个 DAG ，相当于一个在有向无环图（DAG）上求最长路径的问题，每个节点有正权值（地雷数）。所以一开始想到的是拓扑排序，用 BFS 解决，代码如下：
#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)$ ，代码如下：
#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[i] = a[i] + \max_{j>i && connected[i][j]} dp[j] $$
DP 部分代码如下（其他与 DFS 做法相同）：
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]);
}