1255: 【基础】挖地雷的算法
内存限制：512 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：12
解决：3
题目描述
在一个地图上有n个地窖（n<=200）,每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径，并规定路径都是单向的,且保证都是小序号地窖指向大序号地窖，也不存在可以从一个地窖出发经过若干地窖后又回到原来地窖的路径。某人可以从任一处开始挖地雷，然后沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使他能挖到最多的地雷。
如下图所示：圆圈内的1 2 3 4 5 6，代表6个地窖的编号，地窖编号旁边的数字代表这个地窖地雷的数量！
输入
第一行：地窖的个数；
第二行为依次每个地窖地雷的个数；
下面若干行：
xi yi //表示从xi可到yi，xi<yi。
最后一行为"0 0"表示结束。
第二行为依次每个地窖地雷的个数；
下面若干行：
xi yi //表示从xi可到yi，xi<yi。
最后一行为"0 0"表示结束。
输出
第一行输出挖地雷的地窖编号的顺序：k1-k2-…-kv
第二行输出一个整数，代表最多能挖到的地雷的数量
样例输入 复制
6
5 10 20 5 4 5
1 2
1 4
2 4
3 4
4 5
4 6
5 6
0 0样例输出 复制
3-4-5-6
34提示
#include <bits/stdc++.h>
using namespace std;
/*
dp[i]=a[i]+max(dp[j]) j=i+1 ...n ij有通路
dp[n]=a[n] 边界
dp:存储从每个地窖开始最多能挖到的地雷数量
a:存储每个地窖的地雷数量
r:存储第i号地窖去了哪一号地窖
f:存储地窖之间的通路关系
*/
int n, i, j, a[210]={0}, dp[210]={0}, r[210]={0};
bool f[210][210]={false};
int main() {
cin >> n;
//读入地雷数量
for (i = 1; i <= n; i++) {
cin >> a[i];
}
//读入通路关系
int x, y;
while (true) {
cin >> x >> y;
if (x == 0 && y == 0) break;
f[x][y] = true;
//xy之间有通路
}
//边界:从最后一个地窖开始最多能挖到的地雷数就是最后一个地窖的地雷数
dp[n] = a[n];
//index:存放i号地窖应该去哪个地窖
//count:编号>i的地窖中，有通路的情况下，哪个地窖开始挖到的地雷最多，存地雷数
int index, count; //逆推
for (i = n - 1; i >= 1; i--) {
/*
从第i个地窖开始应该去哪个地窖取决于:
从i+1~n之间的地窖中有通路的地窖，从哪个地窖开始挖，得到的地雷最多
*/
count = 0;
for (j = i + 1; j <= n; j++) {
//如果ij有通路，且从j开始挖到的地雷更多
if (f[i][j] == true && dp[j] > count) {
index = j;
count = dp[j];
}
}
//记录从i开始最多能挖到的地雷数量
dp[i] = a[i] + count;
//存储弟i号地窖，去了哪个编号的地窖
r[i] = index;
}
//求从哪个地窖出发:求dp数组最大值的下标
index = 1;
for (i = 2; i <= n; i++) {
if (dp[i] > dp[index])
index = i;
}
int ans = dp[index]; //最多地雷数
//打印路径
while (index != 0) {
cout << index;
index = r[index]; //求出index编号的地窖去了哪里
if (index != 0)
cout << "-";
}
cout << endl << ans;
return 0;
}