← 返回题目列表

AtCoder · awc0056_d

D. 将花坛分成几个部分

中文机器翻译题面 查看原题

分数: 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