分数: 400 分
问题陈述
高桥负责照顾 N 他的花园里排列着一排鲜花。花有编号 1, 2, \ldots, N 从左到右,以及花的高度 i is A_i.
高桥决定问问 K 朋友们分享浇花任务。分配遵循以下规则:
- 划分 N 花成正好 K 非空连续间隔,同时保留其原始顺序。即选择一个整数序列 r_0, r_1, \ldots, r_K 满意 0 = r_0 < r_1 < r_2 < \cdots < r_K = N,其中 j第一个朋友 (1 \leq j \leq K) 负责鲜花来自 r_{j-1}+1 to r_j.
- 的 努力 每个间隔的 被定义为该间隔中包含的花的最大和最小高度之间的差。如果一个区间只包含一朵花,则努力是 0.
- 努力的总和 K 间隔称为 全力以赴.
Takahashi 希望对花朵进行分区,以使总工作量尽可能小。
找到总努力的最小值。
约束
- 1 \leq K \leq N \leq 200
- 1 \leq A_i \leq 1000
- 所有输入均为整数。
输入
N K A_1 A_2 \ldots A_N
- 第一行包含一个整数 N 代表鲜花的数量和一个整数 K 表示间隔数,以空格分隔。
- 第二行包含 N 整数 A_1, A_2, \ldots, A_N 代表花朵的高度 1, 2, \ldots, N,用空格分隔。
输出
在一行上打印总工作量的最小值。
示例输入 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