概要

\(N\) 本の花を並び順を保ったまま \(K\) 個の連続区間に分割し、各区間の「最大値 − 最小値」の合計（総手間）を最小化する問題です。区間分割の最適化問題を動的計画法（DP）で解きます。

考察

重要な気づき

• 花を並び替えることはできず、連続した区間にしか分割できません。つまり、分割点の位置を \(K-1\) 個選ぶ問題と等価です。
• 区間 \([i, j]\) の手間（コスト）は、その区間内の \(\max - \min\) で一意に決まります。これは事前に全ペアについて計算しておけます。
• 分割点の候補は膨大ですが、最適部分構造を持っています。「最初の \(i\) 本の花を \(k\) 個の区間に分ける最小コスト」を求めれば、そこに1区間追加する形で拡張できます。

素朴なアプローチでは？

全ての分割方法を列挙すると、分割点の選び方は \(\binom{N-1}{K-1}\) 通りあり、\(N\) や \(K\) が大きいと指数的に増えてしまいます。しかし \(N \leq 200\) という制約から、\(O(N^2 K)\) の DP で十分間に合います。

アルゴリズム

ステップ1：区間コストの前計算

すべての区間 \([i, j]\)（\(0 \leq i \leq j < N\)、0-indexed）について、\(\text{cost}[i][j] = \max(A_i, \ldots, A_j) - \min(A_i, \ldots, A_j)\) を計算します。

\(i\) を固定して \(j\) を \(i\) から \(N-1\) まで増やしながら、最大値・最小値を更新していけば \(O(N^2)\) で全区間のコストが求まります。

ステップ2：動的計画法

状態定義： \(dp[k][i]\) = 最初の \(i\) 本の花（花 \(1\) 〜 花 \(i\)）をちょうど \(k\) 個の区間に分割したときの総手間の最小値。

初期条件： \(dp[0][0] = 0\)（花が0本で区間0個、手間は0）

遷移： \(k\) 個目の区間が花 \(j+1\) 〜 花 \(i\) を担当するとすると：

\[dp[k][i] = \min_{j=k-1}^{i-1} \left( dp[k-1][j] + \text{cost}[j][i-1] \right)\]

ここで \(j\) は「最初の \(k-1\) 個の区間で担当する花の本数」を表します。\(j \geq k-1\) なのは、\(k-1\) 個の区間にはそれぞれ少なくとも1本必要だからです。

答え： \(dp[K][N]\)

具体例

\(N=5, K=2, A=[3, 1, 4, 1, 5]\) の場合：

• 分割 \([3,1,4,1] | [5]\) → 手間 \((4-1) + 0 = 3\)
• 分割 \([3,1] | [4,1,5]\) → 手間 \((3-1) + (5-1) = 6\)
• 分割 \([3] | [1,4,1,5]\) → 手間 \(0 + (5-1) = 4\)

このようにすべての分割点を DP で効率的に探索し、最小値を求めます。

計算量

• 時間計算量: \(O(N^2 K)\)（前計算 \(O(N^2)\) + DP 遷移 \(O(N^2 K)\)）
  • \(N \leq 200, K \leq 200\) なので最大 \(200^2 \times 200 = 8 \times 10^6\) 程度で十分高速です。
• 空間計算量: \(O(N^2 + NK)\)（コストテーブル \(O(N^2)\) + DPテーブル \(O(NK)\)）

実装のポイント

• cost[i][j] は 0-indexed で花 \(i+1\) 〜 花 \(j+1\) に対応するため、DP 遷移で cost[j][i-1] のようにインデックスをずらす点に注意が必要です。

• DP の初期値を INF（十分大きい値）にしておき、到達不可能な状態からの遷移を防ぎます。

• \(k\) 個の区間にはそれぞれ最低1本必要なので、\(i\) のループ範囲を k 以上、\(j\) のループ範囲を k-1 以上とする下限の制約を忘れないようにしましょう。

  ソースコード

import sys

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    # Precompute cost for interval [i, j] (0-indexed, inclusive)
    cost = [[0] * N for _ in range(N)]
    for i in range(N):
        mn = mx = A[i]
        for j in range(i, N):
            mn = min(mn, A[j])
            mx = max(mx, A[j])
            cost[i][j] = mx - mn
    
    # DP: dp[k][i] = minimum total cost to partition first i flowers into k intervals
    # i is 1-indexed (number of flowers), k is number of intervals
    INF = float('inf')
    dp = [[INF] * (N + 1) for _ in range(K + 1)]
    dp[0][0] = 0
    
    for k in range(1, K + 1):
        for i in range(k, N + 1):
            for j in range(k - 1, i):
                # j flowers in first k-1 intervals, flowers j+1..i in k-th interval
                if dp[k-1][j] < INF:
                    dp[k][i] = min(dp[k][i], dp[k-1][j] + cost[j][i-1])
    
    print(dp[K][N])

main()

---

この解説は claude4.6opus-thinking によって生成されました。