JOI難易度６ オレンジの出荷

問題原文

atcoder.jp

問題要旨

個のオレンジが横１列に並んでいる。 番目のオレンジの大きさは である。
このオレンジの列をいくつかの区間に分割し、箱詰めすることを考える。箱には最大で 個のオレンジがあり、１つにつき のコストがかかる。また、ある箱に詰めるオレンジの数を , オレンジの大きさの最大値と最小値を とするとき、 のコストが追加でかかる。
全てのオレンジを箱に詰める時のコストを最小化せよ。

• 

解法

正しそうな方向に仮置きする感じで考察を進めていく。
番目のオレンジまでを箱に詰める時の最初コストとする。

例えば１つの箱に３つまでオレンジが入るとして、今２番目のオレンジをみているとすると、
「２番目のオレンジを入れる」「２、３番目のオレンジを入れる」「２、３、４番目のオレンジを入れる」ところに配る遷移ができることがわかる。

また、２、３、４番目のオレンジを入れる遷移の前に２、３番目のオレンジを入れる遷移を行っているので、区間 [2, 3] の最大値と最小値は手に入っており、その更新も４番目のオレンジとの比較をするだけで済むことがわかる。

ここまでできればあとは一直線。
各 について、配れる範囲が制限されていることを意識しながら dpテーブルを埋めていけばいい。

実装

あくまでも配るdpであることを意識して実装する。

import sys
my_input = sys.stdin.readline
N, M, K = map(int, my_input().split())
A = [int(my_input()) for _ in range(N)]


# dp[i] := i番目のオレンジを詰めるまでの最小コスト
dp = [float('inf')] * (N + 1)
dp[0] = 0

for i in range(N):
    MAX = MIN = A[i]
    for j in range(i, min(i + M, N)):
        MAX = max(MAX, A[j])
        MIN = min(MIN, A[j])
        dp[j + 1] = min(dp[j + 1], dp[i] + K + (j - i + 1) * (MAX - MIN))

print(dp[-1])

感想

dpの更新途中で一時情報を更新していくみたいな雰囲気なのかな。
好きな問題です。