Python의 대회에서 달성할 수 있는 점수를 찾는 프로그램

<시간/>

여러 문제가 있지만 한 문제를 해결하면 대회가 끝나는 프로그래밍 대회에 참가한다고 가정해 보겠습니다. 이제 포인트와 기회라고 하는 길이가 같은 두 개의 숫자 목록이 있습니다. 그것을 설명하기 위해 여기 i번째 문제에 대해 포인트[i] 포인트에 대해 해결할 확률[i]퍼센트가 있습니다. 우리는 또한 우리가 시도할 수 있는 문제의 수를 나타내는 또 다른 값 k가 있습니다. 같은 문제는 두 번 시도할 수 없습니다.

최적의 전략을 고안하면 가장 가까운 정수로 반올림되는 대회에서 얻을 수 있는 점수의 예상 값을 찾아야 합니다. i 번째 문제를 시도할 때의 값은 points[i] * chances[i] / 100.0으로 예상할 수 있으며 이는 평균적으로 얻을 수 있는 포인트 수를 나타냅니다.

따라서 입력이 포인트=[600, 400, 1000], 기회 =[10, 90, 5], k =2인 경우 출력은 392가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=포인트 크기
0에서 n 사이의 i에 대해 수행
기회[i] :=기회[i] / 100.0
R :=포인트 내림차순으로 정렬된 0-3 정렬
반환 int(dp(0, K))
dp() 함수를 정의합니다. i, k
가 소요됩니다.
- i가 n과 같으면
  - 0.0 반환
- j :=R[i]
- p :=기회[j]
- ev :=p * 포인트[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