Overview

This problem asks us to divide \(N\) flowers into \(K\) contiguous segments while preserving their order, and minimize the total “effort,” which is the sum of (maximum − minimum) for each segment. We solve this interval partition optimization problem using dynamic programming (DP).

Analysis

Key Observations

• The flowers cannot be rearranged; they can only be divided into contiguous segments. In other words, this is equivalent to choosing the positions of \(K-1\) split points.
• The effort (cost) of a segment \([i, j]\) is uniquely determined by \(\max - \min\) within that segment. This can be precomputed for all pairs.
• Although the number of candidate split points is enormous, the problem has optimal substructure. If we find “the minimum cost of dividing the first \(i\) flowers into \(k\) segments,” we can extend it by appending one more segment.

What About a Naive Approach?

Enumerating all possible divisions, there are \(\binom{N-1}{K-1}\) ways to choose split points, which grows exponentially when \(N\) or \(K\) is large. However, given the constraint \(N \leq 200\), an \(O(N^2 K)\) DP is more than fast enough.

Algorithm

Step 1: Precompute Interval Costs

For every interval \([i, j]\) (\(0 \leq i \leq j < N\), 0-indexed), compute \(\text{cost}[i][j] = \max(A_i, \ldots, A_j) - \min(A_i, \ldots, A_j)\).

By fixing \(i\) and increasing \(j\) from \(i\) to \(N-1\) while updating the maximum and minimum, we can compute the costs for all intervals in \(O(N^2)\).

Step 2: Dynamic Programming

State definition: \(dp[k][i]\) = the minimum total effort when dividing the first \(i\) flowers (flower \(1\) through flower \(i\)) into exactly \(k\) segments.

Initial condition: \(dp[0][0] = 0\) (0 flowers with 0 segments, effort is 0)

Transition: Assuming the \(k\)-th segment covers flowers \(j+1\) through \(i\):

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

Here, \(j\) represents “the number of flowers covered by the first \(k-1\) segments.” The constraint \(j \geq k-1\) comes from the fact that each of the \(k-1\) segments needs at least one flower.

Answer: \(dp[K][N]\)

Concrete Example

For \(N=5, K=2, A=[3, 1, 4, 1, 5]\):

• Division \([3,1,4,1] | [5]\) → effort \((4-1) + 0 = 3\)
• Division \([3,1] | [4,1,5]\) → effort \((3-1) + (5-1) = 6\)
• Division \([3] | [1,4,1,5]\) → effort \(0 + (5-1) = 4\)

In this way, the DP efficiently explores all split points and finds the minimum.

Complexity

• Time complexity: \(O(N^2 K)\) (precomputation \(O(N^2)\) + DP transitions \(O(N^2 K)\))
  • Since \(N \leq 200, K \leq 200\), the maximum is about \(200^2 \times 200 = 8 \times 10^6\), which is sufficiently fast.
• Space complexity: \(O(N^2 + NK)\) (cost table \(O(N^2)\) + DP table \(O(NK)\))

Implementation Notes

• cost[i][j] is 0-indexed and corresponds to flowers \(i+1\) through \(j+1\), so be careful to shift indices in the DP transition, using cost[j][i-1] and similar expressions.

• Initialize the DP values to INF (a sufficiently large value) to prevent transitions from unreachable states.

• Since each of the \(k\) segments requires at least one flower, don’t forget the lower bound constraints: the loop range for \(i\) should be at least k, and the loop range for \(j\) should be at least k-1.

  Source Code

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

---

This editorial was generated by claude4.6opus-thinking.