概要

花の列をK個の連続区間に分割し、各区間の最大値と最小値の差の合計（総手間）を最小化する問題です。

考察

問題を解くためには、N本の花をK個の連続区間に分割する全ての可能な方法を調べる必要があります。各区間の手間はその区間に含まれる花の高さの最大値と最小値の差で定義されます。

素朴なアプローチでは、全ての分割方法を列挙すると指数時間かかってしまいます。制約がN, K ≤ 200なので、動的計画法(DP)を用いて効率的に解くことができます。

DPテーブルを以下のように定義します： - dp[i][j]: 最初のi本の花をj個の区間に分割したときの最小総手間

このDPテーブルを埋めることで、最終的にdp[N][K]が求める答えとなります。

アルゴリズム

動的計画法を用いて以下のように計算します：

1. dp[0][0] = 0 （初期状態：花0本を0区間に分割）

2. i本目までの花をj個の区間に分割する場合を考える

3. 最後の区間の開始位置mを変化させながら、最後の区間のコストを計算

   • 最後の区間 [m, i-1] の最小値と最大値を求める
   • コスト = 最大値 - 最小値
   • dp[i][j] = min(dp[i][j], dp[m][j-1] + コスト)

4. 特にj=1の場合は、最初からi本目までを1つの区間に分割する場合なので、区間全体の最大値と最小値の差を直接計算します

計算量

• 時間計算量: \(O(N^3K)\)
  • 3重ループ（i: N, j: K, m: N）と各ループ内で最大値・最小値計算（N）
• 空間計算量: \(O(NK)\)
  • DPテーブルのサイズが(N+1)×(K+1)

実装のポイント

• 初期値としてINF（十分に大きな値）を設定し、到達不可能な状態を表現

• j=1の場合は特別に処理（区間全体の最大値・最小値を計算）

• 3重ループで全ての可能な分割を試す

• 各ループ内で最後の区間の最大値・最小値を毎回計算する必要がある

  ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    k = int(data[1])
    A = list(map(int, data[2:2+n]))
    
    # dp[i][j]: 最初のi個の花をj個の区間に分割したときの最小総手間
    INF = 10**18
    dp = [[INF] * (k+1) for _ in range(n+1)]
    dp[0][0] = 0
    
    for i in range(1, n+1):
        for j in range(1, k+1):
            if j == 1:
                # 1つの区間の場合、最大値と最小値の差を計算
                min_val = A[0]
                max_val = A[0]
                for idx in range(i):
                    min_val = min(min_val, A[idx])
                    max_val = max(max_val, A[idx])
                dp[i][j] = max_val - min_val
            else:
                # 最後の区間の開始位置をmとする（mは0からi-1まで）
                for m in range(j-1, i):
                    # 最後の区間 [m, i-1] の最大値と最小値を計算
                    min_last = A[m]
                    max_last = A[m]
                    for idx in range(m, i):
                        min_last = min(min_last, A[idx])
                        max_last = max(max_last, A[idx])
                    cost_last = max_last - min_last
                    
                    # 状態遷移: dp[m][j-1] + cost_last
                    if dp[m][j-1] + cost_last < dp[i][j]:
                        dp[i][j] = dp[m][j-1] + cost_last
    
    print(dp[n][k])

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。