题目
6029. 射箭比赛中的最大得分
Alice 和 Bob 是一场射箭比赛中的对手。比赛规则如下:
Alice 先射 numArrows 支箭,然后 Bob 也射 numArrows 支箭。
分数按下述规则计算:
箭靶有若干整数计分区域,范围从 0 到 11 (含 0 和 11)。
箭靶上每个区域都对应一个得分 k(范围是 0 到 11),Alice 和 Bob 分别在得分 k 区域射中 ak 和 bk 支箭。如果 ak >= bk ,那么 Alice 得 k 分。如果 ak < bk ,则 Bob 得 k 分
如果 ak = bk = 0 ,那么无人得到 k 分。
例如,Alice 和 Bob 都向计分为 11 的区域射 2 支箭,那么 Alice 得 11 分。如果 Alice 向计分为 11 的区域射 0 支箭,但 Bob 向同一个区域射 2 支箭,那么 Bob 得 11 分。
给你整数 numArrows 和一个长度为 12 的整数数组 aliceArrows ,该数组表示 Alice 射中 0 到 11 每个计分区域的箭数量。现在,Bob 想要尽可能 最大化 他所能获得的总分。
返回数组 bobArrows ,该数组表示 Bob 射中 0 到 11 每个 计分区域的箭数量。且 bobArrows 的总和应当等于 numArrows 。
如果存在多种方法都可以使 Bob 获得最大总分,返回其中 任意一种 即可。
示例 1:
输入:numArrows = 9, aliceArrows = [1,1,0,1,0,0,2,1,0,1,2,0]
输出:[0,0,0,0,1,1,0,0,1,2,3,1]
解释:上表显示了比赛得分情况。
Bob 获得总分 4 + 5 + 8 + 9 + 10 + 11 = 47 。
可以证明 Bob 无法获得比 47 更高的分数。
示例 2:
输入:numArrows = 3, aliceArrows = [0,0,1,0,0,0,0,0,0,0,0,2]
输出:[0,0,0,0,0,0,0,0,1,1,1,0]
解释:上表显示了比赛得分情况。
Bob 获得总分 8 + 9 + 10 = 27 。
可以证明 Bob 无法获得比 27 更高的分数。
题解
动态规划+路径还原
下面的动态规划算法,注意回溯答案的方法。超时了。测试用例是:
50303
[0,3250,1153,4871,1445,2912,7328,5164,485,6393,5457,11845]
class Solution:
def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:
dp = [[0 for _ in range(12)] for _ in range(numArrows+1)]
for i in range(1, numArrows+1):
for j in range(1, 12):
if i > aliceArrows[j]:
dp[i][j] = max(dp[i-aliceArrows[j]-1][j-1] + j, dp[i][j-1])
else:
dp[i][j] = dp[i][j-1]
ret = [0] * 12
total = numArrows
i = numArrows
for j in range(11, 0, -1):
if dp[i][j] != dp[i][j-1]:
ret[j] = aliceArrows[j] + 1
i -= aliceArrows[j] + 1
total -= aliceArrows[j] + 1
ret[0] = total
return ret
二进制枚举
可以采用二进制枚举。参考@wannabeaguard的评论题解:
class Solution(object):
def maximumBobPoints(self, numArrows, aliceArrows):
n = 12
ans = 0
max_score = 0
for i in range(2 ** n):
arrows = [0 for _ in range(n)]
score = 0
for j in range(n):
if i & (2 ** j):
arrows[j] = aliceArrows[j] + 1
score += j
if sum(arrows) <= numArrows and score >= max_score:
arrows[0] += numArrows - sum(arrows)
ans = arrows
max_score = score
return ans
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)