动态规划练习【仅题目】

挖地雷(Mine)

在一个地图上有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

 

 

 

页面: 1 2 3 4 5 6 7 8

点赞