# 2. 题解

• $k = 1$，序列全取中位数
• $k = 2$，同 bzoj1367 sequence，只不过把问题中的上升改成不降（以及不升）
• $k = 3$，预处理 $1 -> i$的不降（以及不升）的最小代价，还有 $i -> n$的不降（以及不升）的最小代价，再枚举转角位置
• $k > 3$，此时 $n \leq 10 ^ 3$，先 $O(n ^ 2 log n)$预处理出 $i -> j$的不降（以及不升）的最小代价，然后跑一个 $O(n ^ 2 k)$的 Dp…

#include <bits/stdc++.h>

#define NS (20005)

using namespace std;

typedef long long LL;

template<typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

int n, k, t[NS], L[NS], R[NS], P[NS], top;

LL ans = LLONG_MAX, S[NS], H[NS], res[NS];

struct N {int d, dep, l, r;} e[NS];

int Merge(int a, int b)
{
if (!a || !b) return a | b;
if (e[a].d < e[b].d) swap(a, b);
e[a].r = Merge(e[a].r, b);
if (e[e[a].l].dep < e[e[a].r].dep) swap(e[a].l, e[a].r);
e[a].dep = e[e[a].r].dep + 1;
return a;
}

int Pop(int a) {return Merge(e[a].l, e[a].r);}

LL Cal(int a)
{
LL l = R[a] - L[a] + 1;
LL ret = S[a] - H[a] - (l >> 1) * e[P[a]].d;
ret += ((l + 1) >> 1) * e[P[a]].d - H[a];
return ret;
}

void WORK()
{
top = 0;
for (int i = 1; i <= n; i += 1)
e[i].d = t[i], e[i].l = e[i].r = e[i].dep = 0;
for (int i = 1; i <= n; i += 1)
{
res[i] = res[i - 1];
top++, L[top] = R[top] = P[top] = i, S[top] = H[top] = t[i];
while (top > 1 && e[P[top]].d < e[P[top - 1]].d)
{
res[i] -= Cal(top) + Cal(top - 1);
S[top - 1] += S[top], H[top - 1] += H[top];
P[top - 1] = Merge(P[top - 1], P[top]);
if (((R[top - 1] - L[top - 1] + 1) & 1)
&& ((R[top] - L[top] + 1) & 1))
{
H[top - 1] -= e[P[top - 1]].d;
P[top - 1] = Pop(P[top - 1]);
}
R[top - 1] = R[top], top--, res[i] += Cal(top);
}
}
}

namespace W1
{
void work()
{
sort(t + 1, t + 1 + n), ans = 0;
for (int i = 1; i <= n; i += 1)
ans += abs(t[i] - t[(n + 1) >> 1]);
}
}

namespace W2
{
void work()
{
WORK(), ans = res[n];
for (int i = 1; i <= n; i += 1) t[i] = -t[i];
WORK(), ans = min(ans, res[n]);
}
}

namespace W3
{
LL pre[2][NS], suf[2][NS];
void work()
{
WORK(), memmove(pre[0], res, sizeof(pre[0]));
for (int i = 1; i <= n; i += 1) t[i] = -t[i];
WORK(), memmove(pre[1], res, sizeof(pre[1]));
for (int i = 1; i <= n; i += 1) t[i] = -t[i];
reverse(t + 1, t + 1 + n);
WORK(), memmove(suf[0], res, sizeof(suf[0]));
for (int i = 1; i <= n; i += 1) t[i] = -t[i];
WORK(), memmove(suf[1], res, sizeof(suf[1]));
for (int i = 1; i <= n; i += 1) t[i] = -t[i];
reverse(suf[0] + 1, suf[0] + 1 + n);
reverse(suf[1] + 1, suf[1] + 1 + n);
for (int i = 1; i <= n + 1; i += 1)
{
ans = min(ans, pre[0][i - 1] + suf[0][i]);
ans = min(ans, pre[1][i - 1] + suf[1][i]);
}
}
}

namespace W4
{
LL m, V[2][1005][1005], f[1005][15][2];
void work()
{
m = n;
for (int i = 1; i <= m; i += 1)
{
WORK();
for (int j = i; j <= m; j += 1) V[0][i][j] = res[j - i + 1];
for (int i = 1; i <= n; i += 1) t[i] = -t[i];
WORK();
for (int i = 1; i <= n; i += 1) t[i] = -t[i];
for (int j = i; j <= m; j += 1) V[1][i][j] = res[j - i + 1];
for (int i = 1; i < n; i += 1) t[i] = t[i + 1];
n--;
}
n = m, memset(f, 0x3f, sizeof(f));
f[0][0][0] = f[0][0][1] = 0;
for (int i = 1; i <= n; i += 1)
for (int j = 1; j < k; j += 1)
for (int l = 0; l <= 1; l += 1)
for (int p = 0; p < i; p += 1)
f[i][j][l] = min(f[i][j][l],
f[p][j - 1][l ^ 1] + V[l][p + 1][i]);
for (int i = 1; i < k; i += 1)
for (int j = 0; j <= 1; j += 1)
ans = min(ans, f[n][i][j]);
}
}

int main(int argc, char const* argv[])
{
IN(n), IN(k);
for (int i = 1; i <= n; i += 1) IN(t[i]);
if (k == 1) W1::work();
else if (k == 2) W2::work();
else if (k == 3) W3::work();
else W4::work();
printf("%lld\n", ans);
return 0;
}