#includeiostream#includestdioh#includestringhusing namespace std;typedef long long ll;const int N = 5e3 + 50;const int INF = 1e9 + 7;#define feri a b forint i = a; i = b; ++iint n k;int hN fN;int main

题目描述

给定一个长度为 $n$ 的序列 $h_i$，你需要把这个序列划分成 $k$ 个连续的子序列，保证每个子序列的长度不小于 $1$ 且不大于 $n/k$。

定义一个子序列的价值为这个子序列中最大值减去最小值的差，你需要最小化这 $k$ 个子序列价值之和。输出最小的这个和。

输入格式

第一行两个整数 $n,k$，表示序列的长度和子序列的个数。

第二行有 $n$ 个整数 $h_i$，表示这个序列。

输出格式

输出一行一个整数，表示最小的 $k$ 个子序列价值之和。

输入输出样例

输入 #1

5 2 1 2 3 4 5

输出 #1

1

输入 #2

8 4 4 4 4 4 4 4 4 4

输出 #2

0

题解

思路：

f[i][j] 表示前 i 个数分成 j 个子序列的最小代价。状态转移方程如下：

f[i][j] = min(f[i][j], f[k][j - 1] + cost(k + 1, i))

其中，cost(l, r) 表示将区间 [l, r] 分成一段的代价，即 max(h[l], h[l + 1], …, h[r]) - min(h[l], h[l + 1], …, h[r])。

代码

时间复杂度 $O(n^3k)$。