找出Python竞赛中可达到的分数的程序
假设我们参加了一场编程竞赛，那里有多个问题，但是当我们解决一个问题时竞赛就结束了。现在，如果我们有两个长度相同的数字列表，称为点和机会。为了说明这一点，在这里针对第i个问题，我们有[i]％的机会可以解决它的点[i]点。我们还有另一个值k，它代表我们可以尝试的问题数量。不能两次尝试相同的问题。
如果我们设计出最佳策略，我们将必须找到比赛中可以得到的分数的期望值，并将其四舍五入为最接近的整数。我们可以将尝试第i个问题的值期望为points[i]*机会[i]/100.0，这表示我们平均获得的点数。
因此，如果输入是点=[600、400、1000]，机会=[10、90、5]，k=2，则输出将是392。
在线示例
让我们看下面的实现以更好地理解-
class Solution:
def solve(self, points, chances, K):
n = len(points)
for i in range(n):
chances[i] /= 100.0
R = sorted(range(n), key=points.__getitem__, reverse=True)
def dp(i, k):
if i == n:
return 0.0
j = R[i]
p = chances[j]
ev = p * points[j]
if k == 1:
return max(ev, dp(i + 1, k))
return max(dp(i + 1, k - 1) * (1 - p) + ev, dp(i + 1, k))
return int(dp(0, K))
ob = Solution()
print (ob.solve([600, 400, 1000], [10, 90, 5], 2))输入值
[600, 400, 1000], [10, 90, 5], 2输出结果
392