题面描述

在一个地图上有N 个地窖（N<=200）,每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径，并规定路径都是单向的,且从编号小的地窖通向编号大的地窖。某人可以从任一处开始挖地雷，然后沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使他能挖到最多的地雷。

【输入格式】

N {地窖的个数}

W1，W2，……WN {每个地窖中的地雷数}

X1，Y1 {表示从X1可到Y1，保证xi<yi}

X2，Y2

……

0 ，0 {表示输入结束}

【输出格式】

K1-K2-……-Kv {挖地雷的顺序}

MAX {最多挖出的地雷数}

【输入样例】Mine.in

6

5 10 20 5 4 5
1 2
1 4
2 4
3 4
4 5
4 6
5 6
0 0

【输出样例】Mine.out

3-4-5-6
34

版本2(AC样例)

<

pre class="font-size:15 line-height:17 lang:c++ decode:true " title="挖地雷 版本2(AC样例)" >#include<bits/stdc++.h>
using namespace std;
//---------题目变量
int n,w[205],xi,yi;
//---------自用变量
//用stl也许并不是什么好主意
vector< set > dj;//dj[目标地窖编号]{通向目标地窖的地窖编号}
vector dp;//动态规划用数组，表示i号地窖的最大地雷数
vector opt;//动态规划用数组，表示i号地窖的最大地雷数
stack optt;
//---------主程序
int main(){
//读入部分，没什么好废话的
cin>>n;
dj.resize(n+5);//保持一点弹性的空间
opt.resize(n+5);
dp.resize(n+5);
for(int i=1;i<=n;i++){
cin>>w[i];
//cout<<"w["<<i<<"] = "<<w[i]<<endl;
}
while(true){
cin>>xi>>yi;
if(xi==0 && yi==0){
break;
}
dj[yi].insert(xi);
//stl的set遍历方法
//调试代码
set::iterator j=dj[yi].begin();

    while(j!=dj[yi].end()){
        int item=*j;
        j++;
    }

}
//--------核心部分 
for(int i=1;i<=n;i++){//从小到大遍历每个地窖 
    //cout<<"i = "<<i<<endl;
    dp[i]=0;
    if(dj[i].size()!=0){//如果有地窖通向当前地窖 
        //stl的set遍历方法
        set<int>::iterator j=dj[i].begin();
        //cout<<"dj["<<i<<"]={";
        while(j!=dj[i].end()){
            int item=*j;
            if(dp[item]>dp[i]){
            //  cout<<item<<" , ";
                dp[i]=dp[item];
                opt[i]=item;
            }
            j++;
        }
        //cout<<"}"<<endl;
    }
    dp[i]+=w[i];
    //cout<<"dp["<<i<<"]="<<dp[i]<<endl;
    //cout<<"END"<<endl;
}
int ans=0,ansi,step=0;
for(int i=1;i<=n;i++){
    if(dp[i]>ans){
        ans=dp[i];
        ansi=i;
    }
}
while(ansi!=0){
    optt.push(ansi);
    ansi=opt[ansi];
    step++;
}
for(int i=0;i<step-1;i++){
    cout<<optt.top()<<"-";
    optt.pop();
}
cout<<optt.top()<<endl;
cout<<ans<<endl;
return 0;

}

版本1(WA)

<

pre class="font-size:16 line-height:18 lang:c++ decode:true" title="挖地雷 版本1(WA)">#include<bits/stdc++.h>
using namespace std;
//---------题目变量
int n,w[205],xi,yi;
//---------自用变量
//用stl也许并不是什么好主意
vector< set > dj;//dj[目标地窖编号]{通向目标地窖的地窖编号}
vector dp;//动态规划用数组，表示i号地窖的最大地雷数
vector opt;//动态规划用数组，表示i号地窖的最大地雷数
//---------主程序
int main(){
//读入部分，没什么好废话的
cin>>n;
dj.resize(n+5);//保持一点弹性的空间
opt.resize(n+5);
for(int i=1;i<=n;i++){
cin>>w[i];
cout<<"w["<<i<<"] = "<<w[i]<<endl;
}
while(true){
cin>>xi>>yi;
if(xi==0 && yi==0){
break;
}
dj[yi].insert(xi);
//stl的set遍历方法
//调试代码
set::iterator j=dj[yi].begin();
cout<<"dj["<<yi<<"]={";
while(j!=dj[yi].end()){
int item=j;
cout<<item<<" , ";
j++;
}
cout<<"}"<<endl;
}
//--------核心部分
for(int i=1;i<=n;i++){//从小到大遍历每个地窖
cout<<"i = "<<i<<endl;
dp[i]=0;
if(dj[i].size()!=0){//如果有地窖通向当前地窖
//stl的set遍历方法
set::iterator j=dj[i].begin();
while(j!=dj[i].end()){
int item=j;
if(w[item]>dp[i]){
dp[i]=w[item];
}
j++;
}
}
dp[i]+=w[i];
cout<<"END"<<endl;
}
int ans=0;
for(int i=1;i<=n;i++){
if(dp[i]>ans){
ans=dp[i];
}
}
cout<<ans<<endl;
return 0;
}