Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

Python에서 벽돌 제거 게임의 최대 점수를 찾는 프로그램

<시간/>

Amal과 Bimal이 게임을 하고 있다고 가정합니다. 그것들은 그 위에 번호가 매겨진 n개의 벽돌을 결정하는 배열 번호를 가지고 있습니다. 이 게임에서 플레이어는 상단에서 하나, 둘 또는 세 개의 벽돌을 선택적으로 제거할 수 있으며 제거된 벽돌에 표시된 숫자가 해당 플레이어의 점수에 추가됩니다. 항상 Amal이 먼저 시작하는 경우 Amal이 최대로 확보할 수 있는 점수를 찾아야 합니다.

따라서 입력이 nums =[1,2,3,4,5]와 같으면 Amal이 벽돌 {1}, {1,2} 또는 {1,2,3}을 제거할 수 있기 때문에 출력은 6이 됩니다. , Amal이 처음 두 개 또는 세 개의 요소를 선택하면 Bimal이 모두 선택하여 최대 점수를 얻을 수 있지만 Amal이 처음에 1을 선택하면 Bimal은 최대 {2,3,4} =9를 취할 수 있고 Amal은 5를 취할 수 있으므로 총 아말의 점수는 1+5 =6입니다.

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

  • INF :=9999
  • n :=숫자 크기
  • 목록 번호 뒤집기
  • temp :=크기가 n이고 0으로 채워지는 배열
  • total :=크기가 n이고 0으로 채워지는 배열
  • 각 인덱스 i 및 값 val(숫자)에 대해 수행
    • total[i] :=total[i-1] + val
  • temp[0] :=숫자[0]
  • temp[1] :=temp[0]+nums[1]
  • temp[2] :=temp[1]+nums[2]
  • 3 ~ n - 1 범위의 i에 대해 다음을 수행합니다.
    • a :=숫자[i]
    • b :=숫자[i] + 숫자[i-1]
    • c :=숫자[i] + 숫자[i-1] + 숫자[i-2]
    • temp[i] :=최대값, b, c
  • 반환 온도[n-1]

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

INF = 99999
def solve(nums):
   n = len(nums)
   nums.reverse()
   temp = [0]*n
   total = [0]*n
   for i, val in enumerate(nums):
      total[i] = total[i-1] + val
   temp[0] = nums[0]
   temp[1] = temp[0]+nums[1]
   temp[2] = temp[1]+nums[2]
   for i in range(3, n):
      a = nums[i]
      b = nums[i] + nums[i-1]
      c = nums[i] + nums[i-1] + nums[i-2]
      temp[i] = max(a, b, c)
   return temp[n-1]

nums = [1,2,3,4,5]
print(solve(nums))

입력

[1,2,3,4,5]

출력

6