P1584 魔杖

    • 19通过
    • 46提交
  • 题目提供者 JOHNKRAM 管理员
  • 评测方式 云端评测
  • 标签 搜索
  • 难度 普及+/提高
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    Smart在春游时意外地得到了一种好东西——一种非常珍贵的树枝。这些树枝可以用来做优质的魔杖!

    选择怎样的切割方式来制作魔杖非常重要,关键问题是——一把魔杖既不能太长、又不能太短,且制作出来的魔杖不能有冲突……

    Smart得到的这些树枝在属性上完全相同。每一根树枝都有n段(用1~n编号),给定了每段的长度L和每段的魔力值M。你可以做的就是选择一段或连续的几段,把它们作为一个整体切下来,再用来制作魔杖。但是一根魔杖的长度不能太长,不能大于给定的值hi;也不能太短,不能小于给定的值low。

    魔杖有一个奇怪的要求:如果某一根魔杖的制作材料是另一根魔杖的一部分,则这两根魔杖之间将发生冲突。比如说树枝有三段,从左到右的长度分别为4、 1、3,Smart需要长度为4到5之间的魔杖。他可以用一根树枝的前两段做出一个长度为5的魔杖,用一根树枝的后两段做出长度为4的魔杖;但他决不能用一根树枝的前两段做了魔杖后再单独使用另一根树枝的第一段做成魔杖,因为前者包含了后者的所有成分,这会导致冲突。

    我们假设Smart可以得到任意多这样的树枝。Smart需要制作出若干个互不冲突的魔杖,使所有魔杖的魔力值之和最大。(魔杖的长度就是组成它的那些段的长度的总和,魔力值亦然)。

    输入输出格式

    输入格式:

    第一行有三个用空格隔开的正整数,分别表示n、low、hi;

    第二行有n个用空格隔开的正整数就是L[1]、L[2]……L[n];

    第三行有n个用空格隔开的正整数就是M[1]、M[2]……M[n]。

    输出格式:

    只用输出一个整数,表示能够获得的魔力值的最大值。

    输入输出样例

    输入样例#1: 复制
    6 4 5
    1 3 3 2 2 1
    2 3 1 4 5 2
    输出样例#1: 复制
    21

    说明

    取[1 3] [3 2] [2 2 1]做成魔杖,得到最大权值2+3+1+4+4+5+2=21。

    对于$100\%$ 的数据,$1\le n\le 1000$ ,$1\le low\le hi\le 2147483647$ ,$l_{i},m_{i}\le 10^5$

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