PTA 挖地雷

题目描述:

在一个地图上有n个地窖（n≤200）,每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径，并规定路径都是单向的,且保证都是小序号地窖指向大序号地窖，也不存在可以从一个地窖出发经过若干地窖后又回到原来地窖的路径。某人可以从任意一处开始挖地雷，然后沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使他能挖到最多的地雷。

输入格式:

第一行：地窖的个数；

第二行：为依次每个地窖地雷的个数；

下面若干行：

xi yi 表示从xi可到yi，xi<yi。

最后一行为”0 0”表示结束。

输出格式:

k1-k2−…−kv 挖地雷的顺序 挖到最多的雷。

输入样例:

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

输出样例:

1
2
3-4-5-6
34

思路:

本题是一个数字三角形模型的动态规划,定义$dp[i]$为到第i个点能挖到的最多地雷数,因为题目保证都是小序号地窖指向大序号地窖,所以转移方程为$dp[j]=max(dp[j],dp[i]+p[j])$($p[j]是点j的地雷数$).本题难点是记录路径.我们可以用一个数组path[i],每次dp方程转移时记录转移到该点的上一个点是谁($path[j]=i$),最后再找到能挖到最多地雷数的那个点,倒序输出path即可.

Hint:

  • 如果wa最后一个点可以试试这个测试样例:
1
2
3
4
3
1 2 100
1 2
0 0
  • 记得要将$dp[i]初始化为p[i]$

代码:

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
#include <iostream>
using namespace std;
int main(){
	int p[205],n,dp[205]={0},path[205]={0},pre[205];
	bool vis[205][205];
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>p[i];
		dp[i]=p[i];
	}
	int u,v;
	while(1){
		cin>>u>>v;
		if(u==0&&v==0)break;
		vis[u][v]=true;//vis[u][v]意思是u这个点可以到v这个点
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(vis[i][j]&&dp[i]+p[j]>dp[j]){
				dp[j]=dp[i]+p[j];
				path[j]=i;//记录路径
			}
		}
	}
	int k,ans=0;
	for(int i=1;i<=n;i++){
		if(dp[i]>ans){
			ans=dp[i];
			k=i;
		}
	}
	pre[0]=k;//pre[i]作用是倒序记录path
	int d=1;
	while(path[k]!=0){
		pre[d]=path[k];
		k=path[k];
		d++;
	}
	cout<<pre[d-1];
	for(int i=d-2;i>=0;i--){
		cout<<"-"<<pre[i];
	}
	cout<<'\n';
	cout<<ans;
}