Chương trình tìm điểm số kỳ vọng trong cuộc thi lập trình trong Python

Cuộc thi có nhiều bài, kết thúc khi giải được 1 bài. Mỗi bài i: cơ hội chances[i]% giải được, đạt points[i] điểm. Có k lần thử, không thử lại bài cũ. Tìm kỳ vọng điểm tối đa (làm tròn nguyên).

Ví dụ: points=[600,400,1000], chances=[10,90,5], k=2 → 392.

Giải pháp

DP tham lam: sắp xếp bài theo điểm giảm dần, DP(i, k) = kỳ vọng tối đa từ bài i với k lần thử:

• ev = p * points[j] (kỳ vọng nếu thử bài j ngay)
• Nếu k=1: max(ev, DP(i+1, 1))
• Ngược lại: max(DP(i+1, k-1)*(1-p) + ev, DP(i+1, k))

Ví dụ minh họa

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))

Đầu vào

[600, 400, 1000], [10, 90, 5], 2

Đầu ra

392