OpenJudge

2922:太空梯--多重背包

总时间限制:
5000ms
单个测试点时间限制:
1000ms
内存限制:
32768kB
描述

      很久很久以前,魔法世界的人们重视于眼前的享乐,失去了探索宇宙,探索未知世界的兴趣,他们经常以急功近利的心态评价一件事:“这对我有什么用呢?”幸好当时的领导人远见卓识,他说:“我们历史上曾经因错失大航海时代,而导致了长达数百年的衰落。今天,我们不能再错失太空时代,我们的征途将是星辰大海!”所以现在的我们才有足够的技术实力建造太空梯进入太空以应对天顶星人的威胁。他们有k1 <= k <= 400)种不同类型的魔法石,每种魔法石的高度为h1 <= h <= 100),数量为c1 <= c <= 10),由于会收到太空辐射而失去魔力,每一种魔法石不能超过这种魔法石的最大建造高度a1 <= a_i <= 40 000),求解利用这些魔法石所能修建的太空梯的最高高度。

输入
第一行为一个整数即k。第2行到第k+1行每一行有三个数,代表每种类型魔法石的特征,即高度h,限制高度a和数量c。
输出
一个整数,即修建太空梯的最大高度。
样例输入
3
7 40 3
5 23 8
2 52 6
样例输出
48
提示
样例说明:
15+21+12
最底下为3块石头2型,中间为3块石头1型,上面为6块石头3型。放置4块石头2型和3块石头1型是不可以的,因为顶端的石头1型的高度超过了40的限制。
来源
BD
全局题号
15504
添加于
2017-07-10
提交次数
14
尝试人数
10
通过人数
10