Overview

Given a row of flowers, divide the interval into \(K\) parts and minimize the total “effort” (difference between maximum and minimum values) of each interval.

Analysis

In this problem, we need to divide the flowers into exactly \(K\) contiguous intervals without changing their order. The “effort” of each interval is defined as the difference between the maximum and minimum flower heights within that interval.

A naive approach of trying all possible ways to divide the intervals would take exponential time, which is impractical. For example, the number of ways to divide \(N\) flowers into \(K\) intervals is extremely large, and brute-force search would never finish in time.

Therefore, we consider using dynamic programming (DP). By solving subproblems based on how intervals are divided, we can find the overall optimal solution.

Furthermore, since we need to compute the “effort” for each interval many times, we can improve efficiency by precomputing the effort for all intervals \([i, j]\) in advance.

Algorithm

1. Precomputation: Interval Effort

First, we precompute the difference between the maximum and minimum flower heights (effort) for each interval \([i, j]\) (inclusive on both ends). This is stored in a two-dimensional array cost[i][j].

Specifically: - For each fixed interval \([i, j]\), we compute it while updating the maximum and minimum values within the interval. - This precomputation can be done in \(O(N^2)\).

2. Dynamic Programming (DP)

Next, we define the DP table as follows:

dp[i][k] := the minimum total effort when dividing the first \(i\) flowers into exactly \(k\) intervals

Initial conditions: - dp[0][0] = 0 (0 flowers and 0 intervals means 0 effort) - All other values are initialized to infinity (INF)

Transition: - dp[i][k] = min_{j < i}(dp[j][k - 1] + cost[j][i - 1])

In other words, we update dp[i][k] by taking the minimum over “the minimum effort of dividing the first \(j\) flowers into \(k-1\) intervals” + “the effort of the remaining interval \([j, i-1]\)”.

The final answer we want is dp[N][K].

Concrete Example

For example, given the following input:

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

By precomputing the effort for each interval and updating the DP table, we ultimately obtain the minimum total effort.

Complexity

• Time complexity: \(O(N^2K)\)
  • Precomputation is \(O(N^2)\)
  • DP transitions are \(O(N^2K)\) (triple nested loop)
• Space complexity: \(O(N^2 + NK)\)
  • cost array is \(O(N^2)\)
  • dp array is \(O(NK)\)

Implementation Notes

• Be careful with interval indexing (whether it is 0-indexed or 1-indexed)

• When updating the DP, check that dp[j][k-1] is not an invalid value (INF)

• Carefully set the loop ranges for the DP to ensure that \(k\) does not exceed \(i\)

  Source Code

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()

---

This editorial was generated by qwen3-coder-480b.