挖地雷——DP

题目描述
在一个地图上有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

解析
每一条路的起点终点都是小的序号指向大的，所以，最后一个是一定后面没路的。
设置dp[i]为第i个地窖能得到的地雷数，则需要考虑是从前面还是后面遍历。
从前面开始，无法找到一个初始值，1号位，2号位都有向前搜的可能。
从后面开始，最后一个位置，一定为定值。
从后往前一次遍历，如果当前指针指向的位置后面接着路，便比出最大值，加上本来有的。
边界dp[i]=w[i] ,w[i]为第i个地窖所藏地雷数dp[i] = max{w[i]+dp[j]}

#include<bits/stdc++.h>
using namespace std;
int a[201][201]={0},w[201],dp[201],pre[201]; 
void print(int k)
{
    if(k==0)
        return;
    print(pre[k]);
    if(pre[k]==0)
        cout<<k;
    else
        cout<<"-"<<k;
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>w[i];
		dp[i]=w[i];
	}
	int x,y;
	
	while(cin>>x>>y && x&&y){
		a[x][y]=1;
	}
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){ //从后面找
			if(a[j][i] &&dp[j]+w[i]>dp[i]&&i!=j){
				dp[i]=dp[j]+w[i];
				pre[i]=j;
			}
		}
	}
	int mmax=-999999999,k;
	for(int i=1;i<=n;i++){
		if(dp[i]>mmax){
			mmax=dp[i];
			k=i;
		}
	}
	cout<<"K:"<<k<<endl; 
	print(k);
	cout<<endl;
	cout<<mmax<<endl;
	return 0;
}