应该是一个很通用的解法。
一个显然的分段 dp：
\(f_{j,i}\) 表示前 \(i\) 个数分 \(j\) 段的方案数，\(f_{j,i}\gets \min\limits_{k=0}^{i -1}f_{j-1,k}+w(k+1,i)\)。
可以滚动数组，\(f_{i}\gets \min\limits_{k=0}^{i -1}g_{k}+w(k+1,i)\)。这是好理解的。
考虑到分段 dp 的价值函数大多数满足决策单调性，然后就发现 \(w(k+1,i)=(i-k)\cdot\max\limits_{r=k+1}^ia_r\) 不满足决策单调性，很好，寄。
考虑 \([1,i]\) 这个前缀中每个下标 \(j\)，求出 \(v_j=\min\limits_{k=j+1}^ia_k\)，那么 \(v\) 显然能够分成若干个连续段，每段 \(v\) 值相等。并且 \(i\to i+1\) 时，这个连续段是好维护的，使用单调栈即可。注意到这个维护顺序和 dp 顺序一样，这也非常好。
考虑一个连续段 \(d=v_l=v_{l+1}=v_{l+2}=\cdots =v_r\)，对于 \(j\in [l,r]\)，\(w(j+1,i)=(i-j)\cdot d\)，所以对于这个段我们只需要找到 \(\min\limits_{l\le j\le r}g_j+d\cdot(i-j)=\min\limits_{l\le j\le r}g_j+d\cdot i-d\cdot j=d\cdot i+\min\limits_{l\le j\le r}g_j-d\cdot j\)。于是对点集 \(\{(j,g_j)\mid j\in [l,r]\}\) 维护一个下凸壳，每次拿斜率为 \(d\) 的直线切这个凸包即可，我们给连续段标号（实际实现可以直接用右端点编号），并求出第 \(l\) 个连续段的切点为 \((p_l,g_{p_l})\)。
那么我们需要对于所有连续段 \(l\)，求出 \(\min\limits_{l}g_{p_l}+(i-l)\cdot v_{p_l}\)，我去，这太典了，这是个关于 \(i\) 的一次函数，直接用李超线段树维护即可。具体来说，当 \(i\to i+1\) 时，可能会合并一些连续段，假如合并的是 \(x,y\) 连续段，那么我们将 \(x,y\) 里面两个下凸壳合并起来（注意使用启发式合并），取最优的 \((p_l,g_{p_l})\) 决策点，将 \(y=g_{p_l}-l\cdot v_{p_l}+v_{p_l}\cdot i\) 加入李超线段树，并删去原本 \(x,y\) 两个下凸壳里面的决策点。
由于要实现删除，所以要用可持久化李超树/可撤销李超线段树。可持久化的话，每个连续段标号为右端点下标，直接从单调栈的栈顶（往前找第一个大于 \(a_i\) 的位置）的版本继承过来就可以了。
复杂度 \(O(kn\log n)\)。
const int K = 110;
const int N = 2e4 + 200;
const int inf = 0x3f3f3f3f;
int n, k, tp, nc, rt[N], a[N], f[N], g[N], st[N];
deque<int> d[N];
bool cr(int i, int j, int k) {
return 1ll * (j - i) * (f[k] - f[j]) - 1ll * (k - j) * (f[j] - f[i]) > 0;
}
void mrg(int i, int j) {
if (d[i].size() < d[j].size()) {
while (!d[i].empty()) {
int k = d[i].back(); d[i].pop_back();
while (d[j].size() > 1) {
int p = d[j].front(), q = *next(d[j].begin());
if (cr(k, p, q)) break;
d[j].pop_front();
}
d[j].push_front(k);
}
} else {
while (!d[j].empty()) {
int k = d[j].front(); d[j].pop_front();
while (d[i].size() > 1) {
int p = d[i].back(), q = *prev(prev(d[i].end()));
if (cr(q, p, k)) break;
d[i].pop_back();
}
d[i].pb(k);
}
d[j].swap(d[i]);
}
}
int cut(int id, int k) {
int l = 0, r = d[id].size() - 1;
while (l < r) {
int mid = (l + r) >> 1, p = d[id][mid], q = d[id][mid + 1];
if (f[p] - k * p >= f[q] - k * q) l = mid + 1;
else r = mid;
}
return f[d[id][l]] - k * d[id][l];
}
#define ls(x) tr[x].lc
#define rs(x) tr[x].rc
#define mid ((l + r) >> 1)
struct LCT { int lc, rc, id; } tr[N << 5];// Li Chao Tree
pi p[N];
int cmp(int x, int y) { return x == y ? 0 : (x > y ? 1 : -1); }
int gety(int id, int x) { return !id ? inf : p[id].fi * x + p[id].se; }
void ins(int l, int r, int s, int rt, int &x) {
tr[x = ++nc] = tr[rt];
int &t = tr[x].id;
if (cmp(gety(s, mid), gety(t, mid)) == -1) swap(s, t);
int fl = cmp(gety(s, l), gety(t, l)), fr = cmp(gety(s, r), gety(t, r));
if (fl == -1 || (!fl && s < t)) ins(l, mid, s, ls(rt), ls(x));
if (fr == -1 || (!fr && s < t)) ins(mid + 1, r, s, rs(rt), rs(x));
}
int qry(int l, int r, int c, int x) {
if (!x) return inf;
int res = gety(tr[x].id, c);
if (l == r) return res;
if (c <= mid) return min(res, qry(l, mid, c, ls(x)));
else return min(res, qry(mid + 1, r, c, rs(x)));
}
int main() {
n = rd(), k = rd();
for (int i = 1; i <= n; i++) a[i] = rd();
memset(f, inf, sizeof(f)), f[0] = 0;
for (int j = 1; j <= k; j++) {
for (int i = 1; i <= nc; i++)
tr[i] = (LCT) { 0, 0, 0 };
tp = nc = 0;
for (int i = 1; i <= n; i++) {
d[i].clear(), d[i].pb(i - 1);
while (tp && a[i] >= a[st[tp]]) mrg(st[tp], i), tp--;
p[i] = mp(a[i], cut(i, a[i]));
ins(1, n, i, rt[st[tp]], rt[i]);
st[++tp] = i, g[i] = qry(1, n, i, rt[i]);
}
for (int i = 1; i <= n; i++) swap(f[i], g[i]);
}
wr(f[n]);
return 0;
}