bzoj#P1739. [Usaco2005 mar]Space Elevator 太空电梯
[Usaco2005 mar]Space Elevator 太空电梯
题目描述
The cows are going to space! They plan to achieve orbit by building a sort of space elevator:
a giant tower of blocks. They have different types of blocks with which to build the tower. Each block of type has height and is available in quantity . Due to possible damage caused by cosmic rays, no part of a block of type can exceed a maximum altitude . Help the cows build the tallest space elevator possible by stacking blocks on top of each other according to the rules.
牛们要到太空去了!他们打算建造一座太空电梯来送他们进入轨道。
有 种方块,第 种有一个特定的高度 ,一定的存量 . 为防宇宙射线的破坏,第 种方块的任何部分不能超过高度 。请用这些方块堆出最高的太空电梯。
输入格式
- Line : A single integer, .
- Lines : Each line contains three space-separated integers: , and . Line describes block type .
- 第一行输入一个整数 。
- 接下来 行,每行输入三个整数 。
输出格式
- Line : A single integer , the maximum height of a tower that can be built.
- 一个整数,表示最大高度。
3
7 40 3
5 23 8
2 52 6
48
样例说明
从底部开始,先放 个方块 ,之后 个方块 ,接下来 个方块 。不能把 个方块 堆到 个方块 上,因为这样最高的方块 的顶部高度超过了 。
数据规模与约定
对于 的数据,,,,。
题目来源
Gold