Overview

This problem asks us to divide a row of flowers into K contiguous segments and minimize the sum of the differences between the maximum and minimum values in each segment (total effort).

Analysis

To solve the problem, we need to examine all possible ways to divide N flowers into K contiguous segments. The effort for each segment is defined as the difference between the maximum and minimum heights of the flowers contained in that segment.

A naive approach that enumerates all possible divisions would take exponential time. Since the constraints are N, K ≤ 200, we can solve this efficiently using dynamic programming (DP).

We define the DP table as follows: - dp[i][j]: the minimum total effort when dividing the first i flowers into j segments

By filling this DP table, the final answer will be dp[N][K].

Algorithm

We compute using dynamic programming as follows:

1. dp[0][0] = 0 (initial state: 0 flowers divided into 0 segments)

2. Consider the case of dividing the first i flowers into j segments

3. Vary the starting position m of the last segment and compute the cost of the last segment

   • Find the minimum and maximum values of the last segment [m, i-1]
   • Cost = maximum - minimum
   • dp[i][j] = min(dp[i][j], dp[m][j-1] + cost)

4. In particular, when j=1, we are dividing the first i flowers into a single segment, so we directly compute the difference between the maximum and minimum of the entire range

Complexity

• Time complexity: \(O(N^3K)\)
  • Triple loop (i: N, j: K, m: N) with maximum/minimum computation (N) inside each loop
• Space complexity: \(O(NK)\)
  • The DP table has size (N+1)×(K+1)

Implementation Notes

• Set INF (a sufficiently large value) as the initial value to represent unreachable states

• Handle the case j=1 specially (compute the maximum/minimum of the entire range)

• Use a triple loop to try all possible divisions

• The maximum and minimum of the last segment need to be computed each time within each loop iteration

  Source Code

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

This editorial was generated by deepseekv3.