[NOIP1996 提高组] 挖地雷（C++，DP）

题目描述

在一个地图上有 $N$ 个地窖 $\le 20)$ ，每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后可以沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。

输入格式

有若干行。

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

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

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

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

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

… …

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

输出格式

有两行

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

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

样例 #1

样例输入 #1

样例输出 #1

1 3 4 5
27

提示

【题目来源】

NOIP 1996 提高组第三题

解题思路：

本题容易忽略的地方就是：所有边都是有向边

所以只能从高向低挖而不能返回

我们先使挖的数量最多，然后再记录路径

要使挖的数量最多，最简单的思路就是暴力搜索DFS

int dfs(int start) {//返回从start开始的最大数量
	int max_num = 0;
	for (int i = 1; i <= n; i++) {
		if (map[start][i]) {//如果连通
			max_num = max(max_num, dfs(i));
		}
	}
	return max_num + num_arr[start];
}

因为本题数据比较水，不会被卡…但是我们还是坚持进行动态规划

按照搜索的思路来看，本题是存在最优子结构的，所以我们逆向推导

（注：dp[i]中存储的是从第i层开始挖得到的最大数量，即dfs(i)）

for (int i = n; i >= 1; i--) {//由深层到浅层逆向推导
	dp[i] = 0;
	for (int j = n; j > i; j--) {//用更深层的dp[j]进行推导得到浅层的dp[i]
		if (map[j][i]) {//如果连通
			dp[i] = max(dp[i], dp[j]);
		}
	}
	dp[i] += num_arr[i];
}

如果解过最长上升子序列的话，会不会觉得有些相似？

接下来实现记录路径的功能

for (int i = n; i >= 1; i--) {//由深层到浅层逆向推导
	int index = -1;
	for (int j = n; j > i; j--) {//用更深层的dp[j]进行推导得到浅层的dp[i]
		if (map[i][j] && dp[i] < dp[j]) {//如果连通 && dp[i] < dp[j]
			dp[i] = dp[j];
			index = j;
		}
	}
	nxt[i] = index;//记录i的后缀为index
	dp[i] += num_arr[i];
}

最后输出路径

void out_put(int i) {
    cout << i;
    while (nxt[i] != -1) {
        i = nxt[i];
        cout << ' ' << i;
    }
}

至此本题说明完毕，AC代码如下

#include <iostream>
using namespace std;
const int max_n = 20;

int num_arr[max_n + 1] = { 0 };//每个地窖中地雷数目
bool map[max_n + 1][max_n + 1] = { false };//存图
int dp[max_n + 1] = { 0 };//动态规划
int nxt[max_n + 1] = { 0 };//存答案路径
int n;

void out_put(int i) {
	cout << i;
	while (nxt[i] != -1) {
		i = nxt[i];
		cout << ' ' << i;
	}
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> num_arr[i];
	for (int i = 1; i <= n - 1; i++) {
		for (int j = i + 1; j <= n; j++) {//存图
			cin >> map[i][j];
		}
	}
	
	for (int i = n; i >= 1; i--) {//由深层到浅层逆向推导
		int index = -1;
		for (int j = n; j > i; j--) {//用更深层的dp[j]进行推导得到浅层的dp[i]
			if (map[i][j] && dp[i] < dp[j]) {//如果连通 && dp[i] < dp[j]
				dp[i] = dp[j];
				index = j;
			}
		}
		nxt[i] = index;//记录i的后缀为index
		dp[i] += num_arr[i];
	}

	int max_index = 1;
	for (int i = 2; i <= n; i++) {
		if (dp[max_index] < dp[i]) max_index = i;
	}
	out_put(max_index);
	cout << '\n' << dp[max_index];
	return 0;
}

当然，还有一种解题思路是正向推导，与逆向推导基本一致

任意节点可以到达5号节点，反之，把所有的有向边逆转后，也可以看成可以从5号节点到达任意节点

正向推导代码如下文章来源地址https://uudwc.com/A/12aXO

#include <iostream>
using namespace std;
const int max_n = 20;

int num_arr[max_n + 1] = { 0 };//每个地窖中地雷数目
bool map[max_n + 1][max_n + 1] = { false };//存图
int dp[max_n + 1] = { 0 };//动态规划
int pre[max_n + 1] = { 0 };//存答案路径
int n;

void out_put(int i) {//递归输出
	if (pre[i]) out_put(pre[i]);
	cout << i << ' ';
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> num_arr[i];
	for (int i = 1; i <= n - 1; i++) {//存图
		for (int j = i + 1; j <= n; j++) {
			cin >> map[i][j];
		}
	}

	for (int i = 1; i <= n; i++) {
		dp[i] = 0;
		for (int j = 1; j < i; j++) {
			if (map[j][i] && dp[i] < dp[j]) {
				dp[i] = dp[j];
				pre[i] = j;//记录前缀
			}
		}
		dp[i] += num_arr[i];
	}

	int max_sum = 0, max_index = 0;
	for (int i = 1; i <= n; i++) {
		if (max_sum < dp[i]) {
			max_sum = dp[i];
			max_index = i;
		}
	}
	if (pre[max_index]) out_put(pre[max_index]);
	cout << max_index << endl;
	cout << max_sum;
	return 0;
}