[算法题]最大输出

[FlexGap]

题目：

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

输入

第一行 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

[xupefei]

楼主描述对吗？从描述来看这就是一个贪婪算法：用伤害最高那个技能 k 次，用一次伤害第二高的技能，再用伤害最高的技能 k 次，如此反复就行。

如果你说的其实是那个技能最多用 k 次，那这就是个动态规划题，是简单版的背包问题。

[newtype0092]

我感觉就是一个固定的公式啊：
(int)(m/(k+1)) * (d1+d2) + (m%(k+1) * d1)
d1 和 d2 分别是最高伤害和次高伤害的技能，用 O(n)遍历即可求出

@xupefei
技能最多只能用 k 次也还是贪婪啊，技能只有一个伤害，按次数计算，完全不存在分支路线，不会涉及动态规划吧。
除非不按次数按魔法消耗来计算，不同技能有不同的魔耗，才是背包问题。

[newtype0092]

公式有点问题，应该是：
(int)(m/(k+1)) * ((d1*k)+d2) + (m%(k+1) * (d1*k))

这道题刚好 m 是 k+1 的倍数，带进去就是
9/(2+1) * ((7*2)+4)

[rrfeng]

明显应该加上 CD 才有难度…

[xupefei]

@newtype0092 你说的对。我在打字的时候还在想，这个背包问题的 Cost 和 value 怎么是一样的，但因为躺在床上人懒，最后打了个“简单版”了事，哈哈😄