解题思路

给定长度为 n 的数组，需要把它划分为 m 个连续区间，使所有区间的“价格波动值”(区间内最大值减最小值)之和最小。 这是一类典型的“划分型动态规划(Partition DP)”问题。

状态设计

• 设 dp[i][k] 表示把前 i 个元素划分成 k 个连续区间时的最小代价。
• 转移：最后一个区间如果是 (j+1 … i)，则

题目内容

某超市有一排 $n$ 个连续的货架，每个货架上摆放的商品有一个单价。超市计划将这排货架分成 $m$ 个连续的促销区域。

每组区域是连续的货架区间，例如可以是第 $2-5$ 个货架,但不能是第 $2-3$ 个和第 $5$ 个货架。

每个促销区域的“价格波动值”定义为该区域内商品单价的最大值减去最小值。特别地，如果单独一个货架成为促销区域，那么它的价格波动值为 $0$ 。

超市希望所有促销区域的价格波动值之和最小，以此吸引更多顾客。请你帮助他们计算将 $n$ 个货架分成 $m$ 个连续区域后，价格波动值之和的最小值。

输入描述

第一行包含两个整数 $n$ 和 $m$ ，分别表示货架的总数和要分成的区域数量.

第二行包含 $n$ 个整数 $a$ ,依次表示从左到右每个货架上商品的单价。 $1<=m<=n<=500,1<=a_i<=1,000,000,000$.

输出描述

一行，一个整数,表示所有区域的价格波动值之和的最小值.

样例1

输入

4 2
3 1 4 2

输出

3

说明

其中一种可行的方法为:将第一个货架分为一个促销区域，将后三个货架分为一个促销区域。促销区 $1$ 的价格波动值为 $0$ ，促销区 $2$ 的价格波动值为 $3$ ，波动值总和为 $3$ .

可以证明没有其他方案可以使波动值总和更小。