概要

花の高さ列 \(A_1,\ldots,A_N\) を順番を保ったままちょうど \(K\) 個の連続区間に分け、各区間の「最大値−最小値」の合計（総手間）を最小化する問題です。

考察

• 区間 \([l,r]\)（連続部分）の手間は、その区間の最大値と最小値が分かれば \( \max(A_l..A_r) - \min(A_l..A_r)\) と一発で計算できます。
• したがって本質は「どこで区切るか」（境界 \(r_1,\ldots,r_{K-1}\) をどこに置くか）の最適化です。

素朴に「区切り方を全探索」すると、区切り位置の候補が膨大（組合せ爆発）で現実的ではありません。
また、DPをしても「区間の手間」を毎回その場で最大・最小を取り直すと、遷移ごとに \(O(N)\) かかって全体が \(O(KN^3)\) になり、無駄が大きくなります。

そこで、 1. すべての区間 \([l,r]\) の手間 \(cost[l][r]\) を前計算しておく（これで遷移時は \(O(1)\) 参照） 2. 「先頭から i 本を k 区間で分けた最小値」という典型的な区間DPを使う

という方針にします。

アルゴリズム

1. 区間コストの前計算

\(cost[l][r] = \max(A_l..A_r) - \min(A_l..A_r)\) を全て求めます（\(0\)-indexed とします）。

各 \(l\) について右端 \(r\) を伸ばしながら最小値・最大値を更新すると、 - 初期：\(mn=mx=A[l]\) - \(r=l,l+1,\ldots,N-1\) と進めて、\(mn=\min(mn,A[r])\), \(mx=\max(mx,A[r])\) - \(cost[l][r]=mx-mn\)

で \(O(N^2)\) で全区間を埋められます。

2. DP（区間分割）

\(dp[k][i]\) を「先頭から \(i\) 本（\(A_0..A_{i-1}\)）をちょうど \(k\) 区間に分けたときの最小総手間」とします。
すると最後の区間を「\(j\) 本目までで区切って、残り \(A_j..A_{i-1}\) を最後の区間にする」と考えられます。

遷移は [ dp[k][i] = \min_{j} \left( dp[k-1][j] + cost[j][i-1] \right) ] ただし区間は空にできないので、\(k-1\) 区間で \(j\) 本を作れる必要があり、コードでは \(j \in [k-1,\, i-1]\) を走らせています。

初期条件は - \(dp[0][0]=0\)（0本を0区間で分ける手間は0） - それ以外は不可能なので \(\infty\)

最終解は \(dp[K][N]\) です。

※実装ではメモリ節約のため \(dp\) を2行（前の \(k-1\) と現在の \(k\)）だけ持つローリング配列にしています。

計算量

• 時間計算量: 前計算 \(O(N^2)\) + DP \(O(KN^2)\) なので全体で \(O(N^2 + KN^2)=O(KN^2)\)
• 空間計算量: \(cost\) が \(O(N^2)\)、DP配列が \(O(N)\) なので \(O(N^2)\)

（制約 \(N \le 200\) なので十分間に合います。）

実装のポイント

• 添字のずれに注意：DPは「先頭から \(i\) 本」を扱うため、最後の区間コスト参照は cost[j][i-1] になります。

• 区間を空にしないために、遷移の \(j\) は range(k-1, i)（\(j \le i-1\)）とします。

• \(\infty\) は十分大きい値（例：10**18）を使い、最小化で更新します。

  ソースコード

import sys

def main():
    it = iter(sys.stdin.read().split())
    N = int(next(it))
    K = int(next(it))
    A = [int(next(it)) for _ in range(N)]

    # cost[l][r] = max(A[l..r]) - min(A[l..r])
    cost = [[0] * N for _ in range(N)]
    for l in range(N):
        mn = mx = A[l]
        for r in range(l, N):
            if A[r] < mn:
                mn = A[r]
            if A[r] > mx:
                mx = A[r]
            cost[l][r] = mx - mn

    INF = 10**18
    dp_prev = [INF] * (N + 1)
    dp_prev[0] = 0

    for k in range(1, K + 1):
        dp = [INF] * (N + 1)
        for i in range(1, N + 1):
            best = INF
            for j in range(k - 1, i):
                v = dp_prev[j] + cost[j][i - 1]
                if v < best:
                    best = v
            dp[i] = best
        dp_prev = dp

    print(dp_prev[N])

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。