#1663. 2667. [cqoi2012]模拟工厂
2667. [cqoi2012]模拟工厂
#2667. [cqoi2012]模拟工厂
题目描述
有一个称为"模拟工厂"的游戏是这样的:在时刻0,工厂的生产力等于1。在每个时刻,你可以提高生产力或者生产商品。如果选择提高生产力,在下一个时刻时工厂的生产力加1;如果选择生产商品,则下一个时刻你所拥有的商品数量增加 p ,其中 p 是本时刻工厂的生产力。
有 n 个订单,可以选择接受或者不接受。第 i 个订单( t i, g i, m i)要求在时刻 _t i_给买家提供 _g i_个商品,事成之后商品数量减少gi,而收入增加 _m i_元。如果接受订单 i ,则必须恰好在时刻 _t i_交易,不能早也不能晚。同一时刻可以接受多个订单,但每个订单只能被接受一次。要求最后的总收入最大。
例如,如果一共有两个订单(5,1,8)和(7,15,3),用如下策略是最优的:时刻0, 1, 2提高生产力(时刻3的生产力为4),然后在时刻3,4生产商品,则在时刻5时将拥有8个商品。此时接受第1个订单(还会剩下7个商品),并且在时刻5,6继续生产商品,则在时刻7时拥有7+4+4=15个商品,正好满足订单2。
输入格式
输入第一行包含一个整数 n ,即订单数目。以下 n 行每行三个整数 t i, g i, m i。
输出格式
输出仅一行,为最大总收入。输出保证在32位带符号整数范围内。
样例
样例输入
2
5 1 8
7 15 3
样例输出
11
数据范围与提示
编号
|
1-3
|
4-6
|
7-10
---|---|---|---
n
|
<=5
|
<=10
|
<=15
t i
|
100
|
100
|
<=100,000
g i
|
10,000
|
10,000
|
<=109
m i
|
10,000
|
10,000
|
<=109