V2EX = way to explore V2EX 是一个关于分享和探索的地方
Sign Up Now For Existing Member Sign In
This topic created in 2103 days ago, the information mentioned may be changed or developed.
题目：
给定个技能，每个技能能打掉对手的血，你一共有次发招的机会，你不能连续使用某一个技能超过次。问你最多能打掉对手多少血。
输入
第一行 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 Jul 26, 2020 via iPhone 楼主描述对吗？从描述来看这就是一个贪婪算法：用伤害最高那个技能 k 次，用一次伤害第二高的技能，再用伤害最高的技能 k 次，如此反复就行。 如果你说的其实是那个技能最多用 k 次，那这就是个动态规划题，是简单版的背包问题。 |
 | 2 newtype0092 Jul 26, 2020 我感觉就是一个固定的公式啊： (int)(m/(k+1)) * (d1+d2) + (m%(k+1) * d1) d1 和 d2 分别是最高伤害和次高伤害的技能，用 O(n)遍历即可求出 @xupefei 技能最多只能用 k 次也还是贪婪啊，技能只有一个伤害，按次数计算，完全不存在分支路线，不会涉及动态规划吧。 除非不按次数按魔法消耗来计算，不同技能有不同的魔耗，才是背包问题。 |
| 3 newtype0092 Jul 26, 2020 公式有点问题，应该是： (int)(m/(k+1)) * ((d1*k)+d2) + (m%(k+1) * (d1*k)) 这道题刚好 m 是 k+1 的倍数，带进去就是 9/(2+1) * ((7*2)+4) |
 | 4 rrfeng Jul 26, 2020 via Android 明显应该加上 CD 才有难度… |
| 5 xupefei Jul 26, 2020 @newtype0092 你说的对。我在打字的时候还在想，这个背包问题的 Cost 和 value 怎么是一样的，但因为躺在床上人懒，最后打了个“简单版”了事，哈哈 |
Select Language