P1717 钓鱼

    • 1.5K通过
    • 3.8K提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 贪心
  • 难度 普及+/提高
  • 时空限制 1000ms / 128MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    话说发源于小朋友精心设计的游戏被电脑组的童鞋们藐杀之后非常不爽,为了表示安慰和鼓励,VIP999 决定请他吃一次“年年大丰收”,为了表示诚意,他还决定亲自去钓鱼。

    但是,因为还要准备 NOIP2013, z老师只给了他 $H$ 个小时的空余时间,假设有 $n$ 个鱼塘都在一条水平路边,从左边到右编号为 1, 2, 3 .. n 。

    VIP是个很讲究效率的孩子,他希望用这些时间钓到尽量多的鱼。他从湖1出发,向右走,有选择的在一些湖边停留一定的时间钓鱼,最后在某一个湖边结束钓鱼。他测出从第 $i$ 个湖到 $i+1$个湖需要走 $5 \times t_i$ 分钟的路,还测出在第 $i$ 个湖边停留,第一个5分钟可以钓到鱼 $f_i$,以后再每钓5分钟鱼,鱼量减少 $d_i$。为了简化问题,他假定没有其他人钓鱼,也不会有其他因素影响他钓到期望数量的鱼。请编程求出能钓最多鱼的数量。

    输入输出格式

    输入格式:

    第一行:湖的数量n。

    第二行:时间h(小时)。

    第三行:n个数,$f_1$,$f_2$,… $f_n$。

    第四行:n个数,$d_1$,$d_2$,….$d_n$。

    第五行:n-1个数,$t_1$,$t_2$,….$t_{n-1}$

    输出格式:

    一个数,所能钓鱼的最大数量。

    输入输出样例

    输入样例#1: 复制
    2
    1
    10  1
    2  5
    2
    
    输出样例#1: 复制
    31

    说明

    1 <= H <= 16

    2 <= n <= 25

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。