这是一个创建于 1363 天前的主题，其中的信息可能已经有所发展或是发生改变。
题目：
给定𝑛个技能，每个技能能打掉对手𝑎𝑖的血，你一共有𝑚次发招的机会，你不能连续使用某一个技能超过𝑘次。问你最多能打掉对手多少血。
输入
第一行 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
 |
1
xupefei 2020-07-26 16:26:32 +08:00 via iPhone
楼主描述对吗？从描述来看这就是一个贪婪算法：用伤害最高那个技能 k 次，用一次伤害第二高的技能，再用伤害最高的技能 k 次，如此反复就行。
如果你说的其实是那个技能最多用 k 次，那这就是个动态规划题，是简单版的背包问题。 |
 |
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 次也还是贪婪啊，技能只有一个伤害，按次数计算，完全不存在分支路线，不会涉及动态规划吧。 除非不按次数按魔法消耗来计算，不同技能有不同的魔耗，才是背包问题。 |
|
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) |
 |
4
rrfeng 2020-07-26 16:46:21 +08:00 via Android
明显应该加上 CD 才有难度…
|
|
5
xupefei 2020-07-26 16:58:10 +08:00
@newtype0092 你说的对。我在打字的时候还在想，这个背包问题的 Cost 和 value 怎么是一样的，但因为躺在床上人懒，最后打了个“简单版”了事，哈哈😄
|
Select Language