Overview

Given a sequence of flower heights \(A_1,\ldots,A_N\), the problem asks to divide it into exactly \(K\) contiguous segments while preserving the order, and minimize the total effort, where the effort of each segment is defined as “maximum value − minimum value.”

Analysis

• The effort of a segment \([l,r]\) (contiguous portion) can be computed in one shot as \(\max(A_l..A_r) - \min(A_l..A_r)\), as long as we know the maximum and minimum of that segment.
• Therefore, the essence of the problem is optimizing “where to place the boundaries” (choosing boundaries \(r_1,\ldots,r_{K-1}\)).

Naively enumerating all possible ways to partition leads to a combinatorial explosion, which is impractical.
Also, even with DP, if we recompute the maximum and minimum of each segment from scratch during each transition, each transition costs \(O(N)\), making the total \(O(KN^3)\), which is wasteful.

Therefore, we adopt the following approach: 1. Precompute the effort \(cost[l][r]\) for all segments \([l,r]\) (so that each transition can reference it in \(O(1)\)) 2. Use a classic interval-partition DP: “the minimum cost of dividing the first \(i\) elements into \(k\) segments”

Algorithm

1. Precomputation of Segment Costs

Compute \(cost[l][r] = \max(A_l..A_r) - \min(A_l..A_r)\) for all pairs (\(0\)-indexed).

For each \(l\), extend the right endpoint \(r\) while updating the minimum and maximum: - Initialize: \(mn=mx=A[l]\) - For \(r=l,l+1,\ldots,N-1\), update \(mn=\min(mn,A[r])\), \(mx=\max(mx,A[r])\) - \(cost[l][r]=mx-mn\)

This fills in all segments in \(O(N^2)\).

2. DP (Interval Partition)

Define \(dp[k][i]\) as “the minimum total effort when dividing the first \(i\) elements (\(A_0..A_{i-1}\)) into exactly \(k\) segments.”
Then, consider making the last segment by splitting after the first \(j\) elements, so that \(A_j..A_{i-1}\) forms the last segment.

The transition is: [ dp[k][i] = \min_{j} \left( dp[k-1][j] + cost[j][i-1] \right) ] Since segments cannot be empty, we need \(k-1\) segments to cover \(j\) elements, so in the code \(j\) ranges over \([k-1,\, i-1]\).

Initial conditions: - \(dp[0][0]=0\) (dividing 0 elements into 0 segments costs 0) - Everything else is impossible, so set to \(\infty\)

The final answer is \(dp[K][N]\).

In the implementation, to save memory, only two rows of \(dp\) are maintained (the previous \(k-1\) and current \(k\)) using a rolling array.

Complexity

• Time complexity: Precomputation \(O(N^2)\) + DP \(O(KN^2)\), so overall \(O(N^2 + KN^2)=O(KN^2)\)
• Space complexity: \(cost\) is \(O(N^2)\), DP array is \(O(N)\), so \(O(N^2)\)

(Given the constraint \(N \le 200\), this is well within the time limit.)

Implementation Notes

• Be careful with index offsets: since the DP handles “the first \(i\) elements,” the last segment’s cost reference becomes cost[j][i-1].

• To prevent empty segments, \(j\) in the transition should be range(k-1, i) (i.e., \(j \le i-1\)).

• Use a sufficiently large value for \(\infty\) (e.g., 10**18) and update via minimization.

  Source Code

import sys

def main():
    it = iter(sys.stdin.read().split())
    N = int(next(it))
    K = int(next(it))
    A = [int(next(it)) for _ in range(N)]

    # cost[l][r] = max(A[l..r]) - min(A[l..r])
    cost = [[0] * N for _ in range(N)]
    for l in range(N):
        mn = mx = A[l]
        for r in range(l, N):
            if A[r] < mn:
                mn = A[r]
            if A[r] > mx:
                mx = A[r]
            cost[l][r] = mx - mn

    INF = 10**18
    dp_prev = [INF] * (N + 1)
    dp_prev[0] = 0

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

    print(dp_prev[N])

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.