V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
FlexGap
V2EX  ›  算法

[算法题]最大输出

  •  
  •   FlexGap · 2020-07-26 15:08:45 +08:00 · 1253 次点击
    这是一个创建于 925 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目:

    给定𝑛个技能,每个技能能打掉对手𝑎𝑖的血,你一共有𝑚次发招的机会,你不能连续使用某一个技能超过𝑘次。问你最多能打掉对手多少血。

    输入

    第一行 3 个数 n,m,k,(2<=n<=2*10^5,1<=m,k<=10^9) 第二行 n 个数 a[1...n],(1<=a[i]<=10^9)

    输出

    一个数,表示最大值。

    输入样例

    6 9 2

    1 3 3 7 4 2

    输出样例

    54

    想了半天不知道该怎么写,似乎需要用到动态规划?求大神给个思路 orz

    5 条回复    2020-07-26 16:58:10 +08:00
    xupefei
        1
    xupefei  
       2020-07-26 16:26:32 +08:00 via iPhone
    楼主描述对吗?从描述来看这就是一个贪婪算法:用伤害最高那个技能 k 次,用一次伤害第二高的技能,再用伤害最高的技能 k 次,如此反复就行。

    如果你说的其实是那个技能最多用 k 次,那这就是个动态规划题,是简单版的背包问题。
    newtype0092
        2
    newtype0092  
       2020-07-26 16:39:33 +08:00
    我感觉就是一个固定的公式啊:
    (int)(m/(k+1)) * (d1+d2) + (m%(k+1) * d1)
    d1 和 d2 分别是最高伤害和次高伤害的技能,用 O(n)遍历即可求出

    @xupefei
    技能最多只能用 k 次也还是贪婪啊,技能只有一个伤害,按次数计算,完全不存在分支路线,不会涉及动态规划吧。
    除非不按次数按魔法消耗来计算,不同技能有不同的魔耗,才是背包问题。
    newtype0092
        3
    newtype0092  
       2020-07-26 16:43:37 +08:00
    公式有点问题,应该是:
    (int)(m/(k+1)) * ((d1*k)+d2) + (m%(k+1) * (d1*k))

    这道题刚好 m 是 k+1 的倍数,带进去就是
    9/(2+1) * ((7*2)+4)
    rrfeng
        4
    rrfeng  
       2020-07-26 16:46:21 +08:00 via Android
    明显应该加上 CD 才有难度…
    xupefei
        5
    xupefei  
       2020-07-26 16:58:10 +08:00
    @newtype0092 你说的对。我在打字的时候还在想,这个背包问题的 Cost 和 value 怎么是一样的,但因为躺在床上人懒,最后打了个“简单版”了事,哈哈😄
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   实用小工具   ·   1295 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 45ms · UTC 19:19 · PVG 03:19 · LAX 11:19 · JFK 14:19
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.