#BZOJ2667. 模拟工厂
-
ID: 1131
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
root
模拟工厂
No submission language available for this problem.
题目描述
有一个称为“模拟工厂”的游戏是这样的：在时刻0，工厂的生产力等于1。在每个时刻，你可以提高生产力或者生产商品。如果选择提高生产力，在下一个时刻时工厂的生产力加1；如果选择生产商品，则下一个时刻你所拥有的商品数量增加p，其中p是本时刻工厂的生产力。
有n个订单，可以选择接受或者不接受。第i个订单(ti, gi, mi)要求在时刻ti给买家提供gi个商品，事成之后商品数量减少gi，而收入增加mi元。如果接受订单i，则必须恰好在时刻ti交易，不能早也不能晚。同一时刻可以接受多个订单，但每个订单只能被接受一次。要求最后的总收入最大。
例如，如果一共有两个订单(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行每行三个整数ti, gi, mi。
输出格式
输出仅一行，为最大总收入。输出保证在32位带符号整数范围内。
2
5 1 8
7 15 3
11
数据范围与约定
编号 <o:p></o:p> |
1-3 <o:p></o:p> |
4-6 <o:p></o:p> |
7-10 <o:p></o:p> |
n <o:p></o:p> |
<=5 <o:p></o:p> |
<=10 <o:p></o:p> |
<=15 <o:p></o:p> |
ti <o:p></o:p> |
100 <o:p></o:p> |
100 <o:p></o:p> |
<=100,000 <o:p></o:p> |
gi <o:p></o:p> |
10,000 <o:p></o:p> |
10,000 <o:p></o:p> |
<=109 <o:p></o:p> |
mi <o:p></o:p> |
10,000 <o:p></o:p> |
10,000 <o:p></o:p> |
<=109 <o:p></o:p> |