信息学奥赛一本通 1262：【例9.6】挖地雷 动态规划基本型_c++在一个地图上有 n 个地窖(n<=200),每个地窖中埋有一定数量的地雷。同时,给出地

1262：【例9.6】挖地雷

时间限制: 1000 ms         内存限制: 65536 KB

【题目描述】

【输入】

【输出】

【输入样例】

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;
int n;
int a[205];//地雷数
int b[205];//b[i]表示到第i个地窖，从b[i]号地窖来的路径上雷最多
int c[205];//c[i]表示到第i个地窖，雷最多路径上的雷的数量
bool jh=0;//第一个地窖编号前没有减号
struct node {
    int x;
    int y;
};
node d[40005];
void myprint(int x){
    if (x==0) return;//没有前一个地窖了
    myprint(b[x]);
    if (jh==0){//没有减号
        jh=1;//下次就有减号了
    }else{
        cout<<'-';//输出减号
    }
    cout<<x;
}
bool cmp(node x,node y){
    return x.x<y.x;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int x,y;
    int cnt=0;
    while (cin>>x>>y){
        if (x==0&&y==0) break;
        cnt++;
        d[cnt].x=x;
        d[cnt].y=y;
    }
    //按开始地窖从小到大排序，保证当计算当前地窖时，
    //所有通往当前地窖的路径都已经计算完成
    sort(d+1,d+1+cnt,cmp);//出发地窖从小到大排序
    for(int i=1;i<=cnt;i++){
        x=d[i].x;
        y=d[i].y;
        if (c[x]+a[x]>c[y]){//如果从x来路径上的雷比其他路径上多
            c[y]=c[x]+a[x];//记录最多得雷
            b[y]=x;//记录路径
        }
    }
    int k=0;
    int ans=0;
    for(int i=1;i<=n;i++){//枚举每一个地窖
        if (a[i]+c[i]>ans){//取最大值
            ans=a[i]+c[i];
            k=i;//最后一个地窖
        }
    }
    myprint(k);//递归打印路径
    cout<<endl<<ans;
	return 0;
}