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