โปรแกรมหาคะแนนคาดหวังในการแข่งขันเขียนโปรแกรมใน Python

คำอธิบายโจทย์

การแข่งขันจบเมื่อแก้โจทย์ได้ 1 ข้อ มีโจทย์หลายข้อ points[i], chances[i]% โอกาสแก้ได้ ลองได้สูงสุด k ข้อ (ไม่ซ้ำ) หาคะแนนคาดหวังสูงสุด ปัดจำนวนเต็ม

ตัวอย่าง

points=[600,400,1000], chances=[10,90,5], k=2 → 392

วิธีแก้ปัญหา

DP + Greedy เรียงตาม points มากไปน้อย:

1. แปลง chances เป็น확률 (หาร 100)
2. เรียง index ตาม points descending
3. dp(i, k) = คะแนนคาดหวังสูงสุดจากโจทย์ i..n-1 เหลือโอกาสลอง k ครั้ง
4. Transition: ลองโจทย์ j = R[i] → ev = p*points[j]
   - ถ้า k=1: max(ev, dp(i+1, 1))
   - ถ้า k>1: max(dp(i+1, k-1)*(1-p) + ev, dp(i+1, k))

โค้ด Python

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)
        
        from functools import lru_cache
        
        @lru_cache(None)
        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