西风丶 2016-05-08 16:50 采纳率: 100%
浏览 1725
已采纳

一个简单的背包问题dp

找不出状态转移方程

描述

一大堆期末考试来袭,草滩小王子被迫去上自习了。

除了自习,草滩小王子还想到了n件可以做的事,n件事可以选一些去做,

这些事会花费一定的时间并且必须一次完成不停止(本题中时间的最小单位为1秒)

并且可以提高(降低)草滩小王子自习的效率(神奇的是效率的提升是累加的),

草滩小王子一开始的效率只有1。

草滩小王子可以在任意时刻开始自习任意时间(效率不会因此降低),假设当前的效率为 ki ,

这段时间 ti内获得的收获 si=ti×ki 。

现在草滩小王子共有t秒的时间,该如何分配时间获得最大的自习收获呢。

输入

第一行是一个整数T(T<=10),代表测试数据的组数。 对于每组测试数据: 第一行含两个个整数 t(0≤t≤1000),n(1≤n≤10000) 接下来n行,第行包括2个整数a,b(0≤a≤100,0≤b≤30)。 a代表第i件事所花的时间,b代表第i件事所提升的效率

输出

对于每组测试数据,输出一行,表示草滩小王子能够获得的最大收获

  • 写回答

1条回答 默认 最新

  • 西风丶 2016-05-08 17:01
    关注

    输入
    1
    20 3
    10 5
    6 2
    5 4

    输出
    75

    hint
    小王子花了5秒钟做完第3件事,然后花15秒钟去自习

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥50 树莓派安卓APK系统签名
  • ¥15 maple软件,用solve求反函数出现rootof,怎么办?
  • ¥65 汇编语言除法溢出问题
  • ¥15 Visual Studio问题
  • ¥15 state显示变量是字符串形式,但是仍然红色,无法引用,并显示类型不匹配
  • ¥20 求一个html代码,有偿
  • ¥100 关于使用MATLAB中copularnd函数的问题
  • ¥20 在虚拟机的pycharm上
  • ¥15 jupyterthemes 设置完毕后没有效果
  • ¥15 matlab图像高斯低通滤波