白峻14719雨水


質問する


https://www.acmicpc.net/problem/14719

コード#コード#

h, w = map(int, input().split())

arr = list(map(int, input().split()))
left = [0]*w
left[0] = arr[0]

right = [0]*w
right[-1] = arr[-1]

for i in range(1, w):
    left[i] = max(left[i-1], arr[i])
for i in range(w-2, -1, -1):
    right[i] = max(right[i+1], arr[i])

answer = 0
for i in range(1, w-1):
    if min(left[i], right[i])-arr[i] > 0:
        answer += min(left[i], right[i])-arr[i]
print(answer)

に答える


dpで問題を解いた
左側の配列のiインデックスには、左側がiインデックスより大きいブロックの最大値が含まれ、右側の配列には右側のブロックの最大値が含まれます.
そしてarrでは左[i]と右[i]の小さな値の計算を行いました![]