N개의 요소가 있는 배열 A가 있다고 가정하고 1≤ ax ≤ 10^5 및 1≤ l≤ r≤ N인 두 개의 정수 l과 r도 있습니다. 요소 가져오기 배열에서 ax라고 말하고 제거하고 해당 배열에서 ax+1, ax+2 … ax+R 및 ax-1, ax-2 … ax-L과 동일한 모든 요소를 제거합니다. 이렇게 하면 도끼 점수가 소모됩니다. 배열에서 모든 요소를 제거한 후 총 비용을 최대화해야 합니다.
따라서 입력이 A =[2,4,3,10,5], l =1, r =2인 경우 출력은 18이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
n :=배열의 크기
-
max_val :=0
-
0에서 n 사이의 i에 대해 수행
-
max_val :=max_val의 최대값, 배열[i]
-
-
count_list :=크기의 배열(max_val + 1), 0으로 채움
-
0에서 n 사이의 i에 대해 수행
-
count_list[배열[i]] :=count_list[배열[i]] + 1
-
-
res :=크기의 배열(max_val + 1), 0으로 채움
-
해상도[0] :=0
-
왼쪽 :=왼쪽, 오른쪽의 최소값
-
범위 1에서 max_val + 1까지의 num에 대해 수행
-
k :=num의 최대값 - 왼쪽 - 1, 0
-
res[num] :=res[num - 1]의 최대값, num * count_list[num] + res[k]
-
-
반환 res[max_val]
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def get_max_cost(array, left, right) : n = len(array) max_val = 0 for i in range(n) : max_val = max(max_val, array[i]) count_list = [0] * (max_val + 1) for i in range(n) : count_list[array[i]] += 1 res = [0] * (max_val + 1) res[0] = 0 left = min(left, right) for num in range(1, max_val + 1) : k = max(num - left - 1, 0) res[num] = max(res[num - 1], num * count_list[num] + res[k]) return res[max_val] array = [2,4,3,10,5] left = 1 right = 2 print(get_max_cost(array, left, right))
입력
[2,4,3,10,5] , 1, 2
출력
18