/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
高橋君は、庭に一列に並んだ N 本の花の手入れを担当しています。花には左から順に番号 1, 2, \ldots, N が付いており、花 i の高さは A_i です。
高橋君は、これらの花を K 人の友人に分担して水やりを頼むことにしました。分担は以下のルールに従います：
- N 本の花を、並んでいる順番を保ったまま、ちょうど K 個の空でない連続した区間に分割する。すなわち、0 = r_0 < r_1 < r_2 < \cdots < r_K = N を満たす整数列 r_0, r_1, \ldots, r_K を選び、j 番目 (1 \leq j \leq K) の友人は花 r_{j-1}+1 から花 r_j までを担当する。
- 各区間の 手間 は、その区間に含まれる花の高さの最大値と最小値の差として定義される。区間に花が 1 本だけ含まれる場合、手間は 0 である。
- K 個の区間の手間の合計を 総手間 と呼ぶ。
高橋君は、総手間をできるだけ小さくするように区間分けを行いたいと考えています。
総手間の最小値を求めてください。
制約
- 1 \leq K \leq N \leq 200
- 1 \leq A_i \leq 1000
- 入力はすべて整数である。
入力
N K A_1 A_2 \ldots A_N
- 1 行目には、花の本数を表す整数 N と、分割する区間の数を表す整数 K が、スペース区切りで与えられる。
- 2 行目には、花 1, 2, \ldots, N の高さを表す N 個の整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。
出力
総手間の最小値を 1 行で出力せよ。
入力例 1
5 2 3 1 4 1 5
出力例 1
3
入力例 2
6 3 10 1 10 1 10 1
出力例 2
9
入力例 3
10 4 5 8 3 7 2 9 1 6 4 10
出力例 3
8
入力例 4
20 5 15 3 12 7 20 1 18 5 14 9 2 16 8 11 4 19 6 13 10 17
出力例 4
19
入力例 5
1 1 42
出力例 5
0
Score : 400 pts
Problem Statement
Takahashi is in charge of caring for N flowers arranged in a row in his garden. The flowers are numbered 1, 2, \ldots, N from left to right, and the height of flower i is A_i.
Takahashi has decided to ask K friends to share the task of watering the flowers. The assignment follows these rules:
- Divide the N flowers into exactly K non-empty contiguous intervals while preserving their original order. That is, choose an integer sequence r_0, r_1, \ldots, r_K satisfying 0 = r_0 < r_1 < r_2 < \cdots < r_K = N, where the j-th friend (1 \leq j \leq K) is responsible for flowers from r_{j-1}+1 to r_j.
- The effort of each interval is defined as the difference between the maximum and minimum heights of the flowers contained in that interval. If an interval contains only one flower, the effort is 0.
- The sum of the efforts of the K intervals is called the total effort.
Takahashi wants to partition the flowers so that the total effort is as small as possible.
Find the minimum value of the total effort.
Constraints
- 1 \leq K \leq N \leq 200
- 1 \leq A_i \leq 1000
- All inputs are integers.
Input
N K A_1 A_2 \ldots A_N
- The first line contains an integer N representing the number of flowers and an integer K representing the number of intervals, separated by a space.
- The second line contains N integers A_1, A_2, \ldots, A_N representing the heights of flowers 1, 2, \ldots, N, separated by spaces.
Output
Print the minimum value of the total effort on a single line.
Sample Input 1
5 2 3 1 4 1 5
Sample Output 1
3
Sample Input 2
6 3 10 1 10 1 10 1
Sample Output 2
9
Sample Input 3
10 4 5 8 3 7 2 9 1 6 4 10
Sample Output 3
8
Sample Input 4
20 5 15 3 12 7 20 1 18 5 14 9 2 16 8 11 4 19 6 13 10 17
Sample Output 4
19
Sample Input 5
1 1 42
Sample Output 5
0