P2808 小笼包

    • 32通过
    • 76提交
  • 题目提供者 坚决杀毒2008
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 2014
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    JOI同学的午饭,是在中华料理店买的小笼包。这是一种用小麦粉制成的皮包着馅和热汤的料理,吃的时候,热汤会飞溅出来。

    题目描述

    JOI同学点的小笼包套餐,由馅料不同的N个小笼包组成。 N个小笼包等间隔排成一列,编号为1到N。第i个小笼包与第j个小笼包之间的距离是绝对值| i - j |。 JOI同学按照顺序吃小笼包。最初,所有的小笼包的美味度都是0。吃第i个小笼包时,汤汁向周围飞散,与第i个小笼包距离Di以下的小笼包都淋上了汤汁,而被淋上汤汁的小笼包的美味度会增加Ai。也就是说,吃第i个小笼包的时候,第j个小笼包 (1 ≦ j ≦ N 且 i - Di ≦ j ≦ i + Di)还没有吃到的话,第j个小笼包的美味度就增加Ai。

    JOI 同学要在吃小笼包的顺序上下功夫,让吃的小笼包的美味度的合计最大化。

    输入输出格式

    输入格式:

    输入共3行。

    第1行是1个整数N。

    第2行是N个整数D1, D2, ..., DN (0 ≦ Di ≦ 7) ,以空格分隔。

    第3行是N个整数A1, A2, ..., AN (0 ≦ Ai ≦ 1000),以空格分隔。

    输出格式:

    共1行,输出JOI同学吃的小笼包的美味度的合计最大值。

    输入输出样例

    输入样例#1: 复制
    5
    1 0 1 1 2
    0 2 6 3 4
    输出样例#1: 复制
    20
    输入样例#2: 复制
    10
    5 2 7 2 6 5 3 5 3 6
    8 7 8 4 0 6 0 10 10 0
    输出样例#2: 复制
    237

    说明

    样例1的说明:以第5→第3→第1→第2→第4的顺序吃的话,美味度合计为20,因为美味度超过20的吃法是不存在的,所以这是最好(坠吼)的。

    本题是2014年日本信息学奥林匹克(JOI)预选第6题。

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