Python程序：计算竞赛中可获得的积分

假设我们参加一个编程竞赛，其中有多个问题，但当我们解决一个问题时，竞赛就结束。现在，如果我们有两个相同长度的数字列表，分别称为 points 和 chances。为了解释它，对于第 i 个问题，我们有 chances[i] 的概率以 points[i] 的分数解决它。我们还有一个值 k，表示我们可以尝试的问题数量。同一个问题不能尝试两次。

如果我们设计一个最优策略，我们将不得不找到在竞赛中可以获得的分数的期望值，四舍五入到最接近的整数。我们可以预期尝试第 i 个问题的价值为 points[i] * chances[i] / 100.0，这表示我们平均会获得的分数。

因此，如果输入类似于 points= [600, 400, 1000]，chances = [10, 90, 5]，k = 2，则输出将为 392。

为了解决这个问题，我们将遵循以下步骤：

  • n := points 的大小

  • 对于 i 从 0 到 n，执行：

  • chances[i] := chances[i] / 100.0

  • R := 将 0-3 按照 points 降序排列

  • 返回 int(dp(0, K))

  • 定义一个函数 dp()。它将接收 i 和 k 作为参数

    • 如果 i 等于 n，则

      • 返回 0.0

    • j := R[i]

    • p := chances[j]

    • ev := p * points[j]

    • 如果 k 等于 1，则

      • 返回 ev 和 dp(i + 1, k) 的最大值

    • 返回 dp(i + 1, k - 1) *(1 - p) + ev 和 dp(i + 1, k) 的最大值

示例

让我们看看以下实现以获得更好的理解：

实时演示

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

更新于: 2020-12-23

142 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告