PythonでJOI難易度6を埋める #18

A - オレンジの出荷 (Oranges)

DP．dp[i]を番目までのオレンジを詰めるための最小のcostとして，計算する．

参考にした記事オレンジの出荷 (Oranges) - ia7ck-competitive-programming

from sys import stdin
input = stdin.readline

n, m, k = map(int, input().strip().split())
orange = [int(input().strip()) for _ in range(n)]

inf = float('inf')
dp = [inf for _ in range(n + 1)]
dp[0] = 0
for i in range(1, n + 1): #それぞれのオレンジ
    mx = -inf
    mn = inf
    for j in reversed(range(max(0, i - m), i)): #何個詰めるか
        mx = max(orange[j], mx)
        mn = min(orange[j], mn)
        dp[i] = min(dp[j] + (mx - mn) * (i - j) + k, dp[i])

print(dp[n])