问题 5263 --偷天换日--树型动态规划训练T7

5263: 偷天换日--树型动态规划训练T7

时间限制: 1 Sec  内存限制: 128 MB
提交: 8  解决: 7
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][144kb]

题目描述

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

    神偷对艺术馆内的名画垂涎欲滴准备大捞一把。 艺术馆由若干个展览厅和若干条走廊组成。每一条走廊的尽头不是通向一个展览厅,就

是分为两个走廊。每个展览厅内都有若干幅画,每副画都有一个价值。经过走廊和偷画都是 要耗费时间的。

警察会在 n 秒后到达进口,在不被逮捕的情况下你最多能得到的价值。

输入格式:

第一行一个整数  n(n≤600)。

第二行若干组整数,对于每组整数(t,x),t 表示进入这个展览厅或经过走廊要耗费 t

x 对整数(w,c)表示偷一幅价值为 w 的画需要 c 秒的时间。若秒的时间,若 x>0 表示走廊通向的展览厅内有 x 幅画,接下来

x=0 表示走廊一分为二。(t,c≤5; x≤30)

输入是按深度优先给出的。房间和走廊数不超过 300 个。 输出格式:

仅一个整数,表示能获得的最大价值。 输入样例:

50

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

输出样例:

1500

输入

输出

提示

来源

[提交][状态]