【题目来源】
洛谷：P2196 [NOIP 1996 提高组] 挖地雷 - 洛谷
【题目描述】
在一个地图上有 \(N (N≤20)\) 个地窖，每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后每次可以移动到一个编号比当前节点大且联通的节点去挖地雷，当无满足条件的节点时挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。
【输入】
有若干行。
第 \(1\) 行只有一个数字，表示地窖的个数 \(N\)。
第 \(2\) 行有 \(N\) 个数，分别表示每个地窖中的地雷个数。
第 \(3\) 行至第 \(N+1\) 行表示地窖之间的连接情况：
第 \(3\) 行有 \(n−1\) 个数（\(0\) 或 \(1\)），表示第一个地窖至第 \(2\) 个、第 \(3\) 个 … 第 \(n\) 个地窖有否路径连接。如第 \(3\) 行为 1 1 0 0 0⋯0，则表示第 \(1\) 个地窖至第 \(2\) 个地窖有路径，至第 \(3\) 个地窖有路径，至第 \(4\) 个地窖、第 \(5\) 个 … 第 \(n\) 个地窖没有路径。
第 \(4\) 行有 \(n−2\) 个数，表示第二个地窖至第 \(3\) 个、第 \(4\) 个 … 第 \(n\) 个地窖有否路径连接。
……
第 \(n+1\) 行有 1 个数，表示第 \(n−1\) 个地窖至第 \(n\) 个地窖有否路径连接。（为 \(0\) 表示没有路径，为 \(1\) 表示有路径）。
【输出】
第一行表示挖得最多地雷时的挖地雷的顺序，各地窖序号间以一个空格分隔，不得有多余的空格。
第二行只有一个数，表示能挖到的最多地雷数。
【输入样例】
5
10 8 4 7 6
1 1 1 0
0 0 0
1 1
1
【输出样例】
1 3 4 5
27
【算法标签】
《洛谷 P2196 挖地雷》 #动态规划DP# #搜索# #深度优先搜索DFS# #拓扑排序# #NOIP提高组# #1996#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 25; // 定义最大元素数量int n; // 元素数量
int a[N]; // 存储每个元素的值
int b[N][N]; // 存储元素间的连接关系
int f[N]; // f[i]表示以第i个元素结尾的最大和
int r[N][N]; // r[i]存储以第i个元素结尾的最优路径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 >> b[i][j];}}// 初始化动态规划数组和路径数组for (int i = 1; i <= n; i++){f[i] = a[i]; // 初始值为元素自身r[i][0] = 1; // 路径长度为1r[i][1] = i; // 路径第一个元素为自身}// 动态规划处理for (int i = 1; i < n; i++){for (int j = i + 1; j <= n; j++){if (b[i][j]) // 如果i和j有连接{if (f[i] + a[j] > f[j]) // 如果通过i到达j更优{f[j] = f[i] + a[j]; // 更新最大和memcpy(r[j], r[i], sizeof(r[i])); // 复制路径r[j][0]++; // 增加路径长度r[j][r[j][0]] = j; // 添加当前元素到路径}}}}// 寻找最优解int ans = 0, pos = 0;for (int i = 1; i <= n; i++){if (f[i] > ans){ans = f[i]; // 更新最大和pos = i; // 记录最优解的结束位置}}// 输出最优路径for (int i = 1; i <= r[pos][0]; i++){cout << r[pos][i] << " ";}cout << endl;// 输出最大和cout << f[pos] << endl;return 0;
}
【运行结果】
5
10 8 4 7 6
1 1 1 0
0 0 0
1 1
1
1 3 4 5
27