概要

一列に並んだ花の区間を \(K\) 個に分割し、各区間の「最大値と最小値の差（手間）」の合計を最小にする問題。

考察

この問題では、花を並びを変えずに、ちょうど \(K\) 個の連続した区間に分割する必要があります。各區間の「手間」はその区間に含まれる花の高さの最大値と最小値の差で定義されます。

素朴な方法として、全ての区間の分割方法を試すことを考えると、指数時間かかってしまい現実的ではありません。例えば、\(N\) 個の花を \(K\) 個の区間に分ける組み合わせは非常に多く、全探索では到底間に合いません。

そこで、動的計画法（DP）を使うことを考えます。ある区間をどのように分割するかという情報をもとに、部分問題を解いて全体の最適解を求めることができます。

さらに、各区間の「手間」を何度も求める必要があるため、事前に全ての区間 \([i, j]\) に対する手間を前計算しておくことで効率化できます。

アルゴリズム

1. 前計算：区間の手間

まず、区間 \([i, j]\)（両端含む）の花の高さの最大値と最小値の差（手間）を前もって計算しておきます。これは二次元配列 cost[i][j] に保存します。

具体的には： - 区間 \([i, j]\) を固定して、その中の最大・最小を更新しながら計算します。 - この前計算は \(O(N^2)\) で可能です。

2. 動的計画法（DP）

次に、DPテーブルを以下のように定義します：

dp[i][k] := 最初の \(i\) 個の花をちょうど \(k\) 個の区間に分割したときの最小の総手間

初期条件： - dp[0][0] = 0 （花が0個で区間も0個なら手間は0） - それ以外は無限大（INF）で初期化

更新則： - dp[i][k] = min_{j < i}(dp[j][k - 1] + cost[j][i - 1])

つまり、「最初の \(j\) 個を \(k-1\) 区間に分割した最小手間」＋「残りの区間 \([j, i-1]\) の手間」の最小値を取ることで、dp[i][k] を更新します。

最終的に求めたいのは dp[N][K] です。

具体例

例えば入力が以下の場合：

N=5, K=2
A = [1, 4, 2, 5, 3]

前計算で区間の手間を計算し、DPテーブルを更新していくことで、最終的に最小の総手間を得ます。

計算量

• 時間計算量: \(O(N^2K)\)
  • 前計算が \(O(N^2)\)
  • DPの更新が \(O(N^2K)\)（三重ループ）
• 空間計算量: \(O(N^2 + NK)\)
  • cost 配列が \(O(N^2)\)
  • dp 配列が \(O(NK)\)

実装のポイント

• 区間の添字に注意すること（0-indexed なのか 1-indexed なのか）

• DPの更新において、dp[j][k-1] が無効な値（INF）でないかチェックする

• DPのループ範囲を慎重に設定し、k が i より大きくなりすぎないようにする

  ソースコード

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:]))

    # 前計算: cost[i][j] は区間 [i, j] の手間（0-indexed）
    cost = [[0] * N for _ in range(N)]
    for i in range(N):
        min_h = max_h = A[i]
        for j in range(i, N):
            if A[j] < min_h:
                min_h = A[j]
            if A[j] > max_h:
                max_h = A[j]
            cost[i][j] = max_h - min_h

    # DP: dp[i][k] は最初の i 個の花を k 個の区間に分割したときの最小総手間
    INF = float('inf')
    dp = [[INF] * (K + 1) for _ in range(N + 1)]
    dp[0][0] = 0

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

    print(dp[N][K])

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。