主要内容 #

• 挖地雷
• 求解思路
• 参考代码

1. 挖地雷问题描述 #

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

2. 求解思路 #

1. 确定dp数组的含义
设a[i]存储地窖中地雷数，f[i]以第i个地窖为起点最多可以挖到的地雷数，p[i]记录后续地窖位置。这里的f数组就是我们的dp数组。
由于需要输出路径，因此需要使用p数组来存储当前地窖的下一个地窖的编号。
2. 确定递推公式
f[i]的值从哪来？当然是从与f[i]相连的后续地窖中来。决策：后面有通路的地窖中，选可以挖到地雷数最多的那个。所以状态转移方程： f[i]=max{ a[i]+f[j] | c[i][j]=1, i<j<=n }。
3. dp数组的初始化
由于最后一个地窖没有后续地窖与之相连，所以f[n] = a[n]，同时之前的f[]数组要全部初始化为0。
4. 确定遍历顺序
由于地窖是从小序号推至大序号，所以采用逆推的方式，从最后一个地窖开始倒推至第一个地窖。
5. 举例说明

3. 参考程序 #

#include <iostream<
using namespace std;
#define N 210 
int n;
int x,y; 
int a[N];       // 每个地窖的地雷数
int c[N][N];  	// 两个地窖中是否有通路 
int f[N];       // 以第i个地窖为起点最多可挖到的地雷数
int p[N];       // 后续地窖的位置
int ans,s;    	// ans最大的地雷数，s路径起点编号 
int main()
{
	int i,j;
	int maxn,k;
	
	cin >> n;
	for(i=1;i<=n;i++)		//输入每个地窖中的地雷数 
		cin >> a[i];
	
	while(1) 
	{
        cin >> x >> y;
        if(x == 0 && y == 0)
            break;
		c[x][y]=1;  		//1连通，0不连通
	}
	f[n]=a[n];  // 边界
	for(i=n-1;i>=1;i--)
	{
		k=0;
		maxn=0;
		for(j=i+1;j<=n;j++)
		{
			if(c[i][j]==1 && f[j]>maxn)
			{
				maxn=f[j];
				k=j;
			}
		}
		f[i]=a[i]+maxn;
		p[i]=k;
	}
	ans=f[1];
	s=1;
	for(i=2;i<=n;i++)		//找f[i]中的最大值 
	{
		if(f[i]>ans)
		{
			ans=f[i];
			s=i;
		}
	}
	while(p[s]!=0)			//输出挖雷顺序 
	{
		cout << s << '-';
		s=p[s];
	}
	cout << s << endl;
	cout << ans;
	return 0;
}