Problem5366--偷天换日-训练套题T15T4

5366: 偷天换日-训练套题T15T4

[Creator : ]
Time Limit : 2.000 sec  Memory Limit : 128 MB

Description

4.偷天换日(steal.pas/c/cpp

【问题描述】

神偷对艺术馆内的名画垂涎欲滴准备大捞一把。艺术馆由若干个展览厅和若干条走廊组成。每一条走廊的尽头不是通向一个展览厅,就是分为两个走廊。每个展览厅内都有若干幅画,每副画都有一个价值。经过走廊和偷画都是要耗费时间的。警察会在n秒后到达进口,在不被逮捕的情况下你最多能得到的价值。

【输入文件】

第一行一个整数 n

第二行若干组整数,对于每组整数(t,x),t表示进入这个展览厅或经过走廊要耗费t秒的时间,若x>0表示走廊通向的展览厅内有x幅画,接下来x对整数(w,c)表示偷一幅价值为w的画需要c秒的时间。若x=0表示走廊一分为二。

输入是按深度优先给出的。

【输出文件】

仅一个整数,表示能获得的最大价值。


【输入样例】

50

5 0 10 1 10 1 5 0 10 2 500 1 1000 2 18 1 1000000 4

【输出样例】

1500

【数据规模】

n600

tc5

x30

房间和走廊数不超过300个。

Source/Category