思路:
代码:
/**
@挖地雷(动态规划)
@author 狂热的coder
*/
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#define NUM_SIZE 50
using namespace std;
void clostDist(int n,bool a[NUM_SIZE][NUM_SIZE],int w[NUM_SIZE]){
int d[NUM_SIZE] = {0}; //d[i]表示从第i个地窖开始挖的最多地雷数
d[n] = w[n]; //底部元素固定
int k1,k2;
cin>>k1>>k2;
while(k1&&k2){
a[k1][k2] = true; //a[i][j]表示第i个地窖和第j个地窖是否是通路
cin>>k1>>k2;
}
int sou[NUM_SIZE] = {0}; //记录每个地窖挖雷的路径
for(int i = n-1;i>=1;i--){ //计算每个地窖挖的最多地雷数
int k = 0,max = 0;
for(int j = i+1;j<=n;j++){
if(a[i][j]&&d[j]>max){
max = d[j];
k = j;
}
}
d[i] = max+w[i]; //i号地窖的最大挖雷数
sou[i] = k; //构造i号地窖最大挖雷数的地窖号
}
// for(int i = 1;i<=n;i++){
// cout<<d[i]<<" ";
// }
int fmax = 0,fk = 1;
for(int i = 1;i<=n;i++){ //求出最大挖雷数的地窖
if(d[i]>fmax){
fmax = d[i];
fk = i;
}
}
cout<<"最大挖雷数为: "<<fmax<<endl;
cout<<"挖雷路径为: ";
cout<<fk;
while(sou[fk]){
cout<<"->"<<sou[fk];
fk = sou[fk];
}
}
int main(){
int n;
cin>>n; //地窖数
int w[NUM_SIZE] = {0};
for(int i = 1;i<=n;i++){ //每个地窖的地雷数
cin>>w[i];
}
bool a[NUM_SIZE][NUM_SIZE] = {false};
clostDist(n,a,w);
return 0;
}
/*
6
5 10 20 5 4 5
1 2
1 4
2 4
3 4
4 5
4 6
5 6
0 0
*/
/**
@挖地雷(动态规划)
@a
