P3161 [CQOI2012]模拟工厂

    • 107通过
    • 330提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 模拟 贪心 2012 重庆 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    有一个称为”模拟工厂“的游戏是这样的:在时刻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位带符号整数范围内。

    输入输出样例

    输入样例#1: 复制
    2
    5 1 8
    7 15 3
    输出样例#1: 复制
    11

    说明

    编号        n        ti        gi        mi
    1-3        <=5        100        10000        10000
    4-6        <=10        100        10000        10000
    7-10        <=15        <=100,000    <=10^9        <=10^9
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。