1. 题目

传送门=￣ω￣=

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…

然后就没了。

精简了半天还是有 150 多行

代码：

#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;
}