大型补档计划
就是把序列分成无数段，每段长度 $ >= K$，然后 ([l, r]) 这段的花费是 (S[r] - S[l - 1] - (r - l + 1) * a[l]) （把所有数减成 (a[l])）
很容易列出状态转移方程：
设 (f[i]) 为前 i 个分完段的最小花费
(f[i] = f[j] + s[i] - s[j] - (i - j) * a[j + 1])
移项：
(underline{f[j] - s[j] + j * a[j + 1]}_y = underline{i}_k * underline{a[j + 1]}_x - underline{s[i] + f[i]}_b)
一个鲜明的斜率优化，其中斜率、横坐标都是递增的，用弹出法即可。
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 500005;
const LL INF = 0x3f3f3f3f3f3f3f3f;
int n, K, a[N], q[N];
LL f[N], s[N];
LL inline y(int i) { return f[i] - s[i] + i * (LL)a[i + 1]; }
LL inline x(int i) { return a[i + 1]; }
int main() {
int T; scanf("%d", &T);
while (T--) {
memset(f, 0x3f, sizeof f);
scanf("%d%d", &n, &K);
for (int i = 1; i <= n; i++)
scanf("%d", a + i), s[i] = s[i - 1] + a[i];
f[0] = 0;
int hh = 0, tt = 0;
for (int i = K; i <= n; i++) {
if (i - K >= K) {
while (hh < tt && (y(q[tt]) - y(q[tt - 1])) * (x(i - K) - x(q[tt])) >= (y(i - K) - y(q[tt])) * (x(q[tt]) - x(q[tt - 1]))) tt--;
q[++tt] = i - K;
}
while (hh < tt && y(q[hh + 1]) - y(q[hh]) <= i * (x(q[hh + 1]) - x(q[hh]))) hh++;
if (hh <= tt) f[i] = f[q[hh]] + s[i] - s[q[hh]] - (LL)(i - q[hh]) * a[q[hh] + 1];
}
printf("%lld
", f[n]);
}
return 0;
}