Overview

This problem asks us to split a sequence of \(N\) elements into \(K\) contiguous segments while preserving the order, minimizing the total sum of “difference between maximum and minimum values” across all segments.

Analysis

Problems that involve splitting into contiguous segments and optimizing costs are highly compatible with dynamic programming (DP).

We can anticipate that defining the state as “the minimum cost when dividing the first \(i\) flowers into \(j\) segments” will lead to a solution. Here, if we set the last \(j\)-th segment as “from position \(p+1\) to position \(i\)”, we can perform transitions by adding the cost of that segment (difference between maximum and minimum values).

As a naive approach, if we recompute the maximum and minimum values for every possible segment \([p+1, i]\) from scratch, each transition takes \(O(N)\), resulting in an overall time complexity of \(O(K N^3)\). In languages like Python, this may exceed the time limit (TLE).

To resolve this, it is effective to move the starting position \(p\) of the segment from \(i-1\) leftward in order. Since elements are added one at a time, we can update the maximum and minimum values in \(O(1)\), reducing the overall time complexity to \(O(K N^2)\).

Algorithm

We solve this using dynamic programming (DP). Originally, we would consider a 2D array dp[j][i], but in practice, to save memory, we use a 1D array dp[i] and update it for each loop over \(j\).

We define dp[i] as “the minimum total cost when dividing the first \(i\) flowers into segments, at the previous step (dividing into \(j-1\) segments).”

The transition formula is as follows: $\( \text{new\_dp}[i] = \min_{j-1 \le p < i} \{ \text{dp}[p] + (\text{max of segment } [p+1, i] - \text{min of segment } [p+1, i]) \} \)$

Specific steps: 1. Initialization: Set dp[0] = 0, and all other values to a sufficiently large value (INF). 2. For \(j = 1, 2, \dots, K\) (number of segments), perform the following updates. 3. Initialize a new array new_dp with INF. 4. For \(i = j, j+1, \dots, N\) (number of flowers to divide), examine: 5. Loop the boundary \(p\) of the last segment from \(i-1\) down to \(j-1\) in reverse order (right to left). - At this point, update max_val and min_val, the maximum and minimum flower heights in the segment \([p+1, i]\). - Compute dp[p] + max_val - min_val, and update new_dp[i] if this is smaller than the current minimum. 6. Replace dp with new_dp and proceed to the next \(j\). 7. Finally, dp[N] is the desired minimum total cost.

Complexity

• Time complexity: \(O(K N^2)\)
  • There are \(O(NK)\) states, and for each state’s transition, \(p\) loops at most \(N\) times. Since updating the maximum and minimum values within the loop takes \(O(1)\), the overall time complexity is \(O(K N^2)\). With the constraints \(N, K \le 200\), this amounts to at most \(200 \times 200 \times 200 \approx 8 \times 10^6\) operations, which is sufficiently fast.
• Space complexity: \(O(N)\)
  • Since we only maintain two 1D arrays of length \(N+1\), dp and new_dp, the space complexity is \(O(N)\).

Implementation Notes

• \(O(1)\) updates via reverse-order loop: The key point is moving \(p\) from \(i-1\) in decreasing order. This means we are examining a segment with a fixed right end whose left end extends by one position at a time, so we can update min_val and max_val by comparing just one element each time.

• Array reuse (in-place DP): Even if we allocate a 2D array dp[j][i], the space complexity would be \(O(NK)\), which is not a problem. However, since we only use the results from the previous \(j-1\), preparing two 1D arrays (dp and new_dp) and reusing them results in a more memory-efficient and cache-friendly implementation.

  Source Code

import sys

def main():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    K = int(data[1])
    A = [int(x) for x in data[2:N+2]]
    
    INF = 10**18
    dp = [INF] * (N + 1)
    dp[0] = 0
    
    for j in range(1, K + 1):
        new_dp = [INF] * (N + 1)
        for i in range(j, N + 1):
            min_val = A[i-1]
            max_val = A[i-1]
            res = INF
            for p in range(i - 1, j - 2, -1):
                val = A[p]
                if val < min_val:
                    min_val = val
                elif val > max_val:
                    max_val = val
                
                cost = dp[p] + max_val - min_val
                if cost < res:
                    res = cost
            new_dp[i] = res
        dp = new_dp
        
    print(dp[N])

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3.1-pro-thinking.