/*
*
* 主体思路和AcWing 2725. 数字序列 是一样的,只不过套了一层二维DP
*
*/
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int MAX_NODE_NUN = 2001000;
int ll[MAX_NODE_NUN]; // 左指针
int rr[MAX_NODE_NUN]; // 右指针
int val[MAX_NODE_NUN]; // 实际问题里面节点数值不一定就是int类型,实际使用的时候根据具体情况做修改, 和模板参数T对应即可,需要T类型实现小于运算符
int dis[MAX_NODE_NUN]; // 节点的距离
int __buffer[MAX_NODE_NUN]; // 缓存,并查集操作时候使用
int __pool_pos = 1; // 当前对象池的末尾
// 区间结构体
struct range_node {
int start, end; // 区间开始和结束位置
int root_id; // 左偏树上的根id
int min_part_sum; // 偏小的一半数值的和
int all_sum; // 区间中所有数值的和
// 当前区间中所有数值和区间中位数的差值的绝对值和
int get_cost() {
int mid_val = val[root_id];
int min_part_size = (end - start + 1) / 2 + (end - start + 1) % 2;
return (mid_val * min_part_size - min_part_sum) + (all_sum - min_part_sum - mid_val * (end - start + 1 - min_part_size));
}
} ranges[MAX_NODE_NUN];
int range_idx = 0;
int arr[MAX_NODE_NUN];
int cost[1005][1005];
int dp[1005][11];
template<typename T>
class LeftistHeapForest {
// 合并根是id1和根是id2的两个堆, 返回新堆的堆顶节点的id号
int __merge(int id1, int id2) {
if (id1 == 0 || id2 == 0) {
return id1 + id2;
}
T val1 = val[id1], val2 = val[id2];
if (val2 > val1 || (val1 == val2 && id2 < id1)) {
id1 = id1 ^ id2, id2 = id1 ^ id2, id1 = id1 ^ id2;
}
int new_root_id = __merge(rr[id1], id2);
rr[id1] = new_root_id;
dis[id1] = dis[new_root_id] + 1;
int l_id = ll[id1], r_id = rr[id1];
if (dis[r_id] > dis[l_id]) {
ll[id1] = r_id, rr[id1] = l_id;
}
return id1;
}
public:
LeftistHeapForest() {
__pool_pos = 1;
}
// 用数值v创建新堆, 返回新创建的节点的id
int make_new_heap(T v) {
int id = __pool_pos++;
ll[id] = rr[id] = dis[id] = 0;
val[id] = v;
return id;
}
// 合并堆顶是root1和堆顶是root2的堆, 返回新的堆的堆顶元素的id
int merge(int root1, int root2) {
return __merge(root1, root2);
}
// 获取堆顶是id的节点所在堆的堆顶的元素(堆顶id, 堆顶val)
T get_top_val(int root) {
return val[root];
}
// 将堆顶是root号节点的堆的堆顶元素从堆上删除, 返回(新堆顶id, 弹出去的堆顶val)
pair<int, T> pop_top_val(int root) {
int new_root_id = __merge(ll[root], rr[root]);
return pair<int, T>{new_root_id, val[root]};
}
};
void get_min_cost(int start, int end) {
range_idx = 0;
int node_val, prev_val;
int mid_val; // 当前的中位数
LeftistHeapForest<int> algo;
node_val = arr[start];
ranges[range_idx++] = {0, 0, algo.make_new_heap(node_val), node_val, node_val};
cost[start][start] = 0;
int cur_cost = 0; // 当前所有区间中数值和区间中位数的差值的绝对值和
for (int i = start+1; i <= end; i++) {
node_val = arr[i];
node_val -= (i - start); // a'[i] = a[i] - i 做映射
ranges[range_idx++] = {i-start, i-start, algo.make_new_heap(node_val), node_val, node_val};
cur_cost += ranges[range_idx-1].get_cost();
while (range_idx >= 2) {
node_val = val[ranges[range_idx-1].root_id];
prev_val = val[ranges[range_idx-2].root_id];
if (node_val >= prev_val) {
break;
}
cur_cost -= ranges[range_idx-2].get_cost();
cur_cost -= ranges[range_idx-1].get_cost();
int new_root = algo.merge(ranges[range_idx-1].root_id, ranges[range_idx-2].root_id);
int all_sum = ranges[range_idx-1].all_sum + ranges[range_idx-2].all_sum;
int min_part_sum = ranges[range_idx-1].min_part_sum + ranges[range_idx-2].min_part_sum;
if (((ranges[range_idx-1].end - ranges[range_idx-1].start + 1) & 1) && ((ranges[range_idx-2].end - ranges[range_idx-2].start + 1) & 1)) {
// 两个左偏树大小都是奇数,维护中位数,合并后新的堆会多一个节点
auto ret = algo.pop_top_val(new_root);
new_root = ret.first;
min_part_sum -= ret.second;
}
ranges[range_idx-2] = {ranges[range_idx-2].start, ranges[range_idx-1].end, new_root, min_part_sum, all_sum};
mid_val = val[new_root];
range_idx -= 1;
cur_cost += ranges[range_idx-1].get_cost();
}
cost[start][i] = min(cost[start][i], cur_cost);
}
}
int main() {
//freopen("/Users/grh/Programming/CLionProjects/SimpleTest/input.txt", "r", stdin);
int n, k;
scanf("%d %d",&n, &k);
for (int i = 0; i < n; i++) {
scanf("%d", arr + i);
}
for (int ii = 0; ii < n; ii++) {
for (int jj = ii; jj < n; jj++) {
cost[ii][jj] = 0x7fffffff;
}
}
// 修改为递增序列的最小开销
if (k == 1) {
get_min_cost(0, n-1);
} else {
for (int ii = 0; ii < n; ii++) {
get_min_cost(ii, n - 1);
}
}
for (int i = 0; i < n; i++) {
arr[i] = 0 - arr[i];
}
// 修改成递减序列的最小开销
if (k == 1) {
get_min_cost(0, n-1);
} else {
for (int ii = 0; ii < n; ii++) {
get_min_cost(ii, n - 1);
}
}
if (k == 1) {
printf("%d\n", cost[0][n-1]);
return 0;
}
// dp[i][j] 表示前i个数分成j份单调区间的最小开销
for (int ii = 0; ii < n; ii++) {
dp[ii][1] = cost[0][ii];
for (int kk = 2; kk <= k && kk <= ii+1; kk++) {
int i = ii-1;
dp[ii][kk] = 0x7fffffff;
while (i+1 >= kk-1) {
dp[ii][kk] = min(dp[ii][kk], dp[i][kk-1] + cost[i+1][ii]);
i -= 1;
}
}
}
printf("%d", dp[n-1][k]);
}