【题意】：给出一个长度为n的非递减序列，要你将该序列分组，每组至少k个元素，每组的代价是该组每一个元素减去该组的最小值的和，问分组的最小代价。
【题解】：这类型的题目多数是dp实现的。
设dp[i]表示前 i 个元素分好组的最小代价。
dp[i] = min(dp[j] + sum[i] - sum[j] - (i - j) * val[j+1]), k <= j <= i - k;
考虑到n <= 500000，朴素的dp肯定会超时，优化势在必行。
这题需要用单调队列优化，我也是从这里学到单调队列优化dp的。
这里我不详细证明了，很烦人的。
用单调队列优化之后，复杂度可以降为O(n)。
笼统一点来说就是，维护凸线，然后用O(1)或者O(logn)的时间来取得最优决策。
因为这题满足决策的单调性，所以可以把转移降到O(1)。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 #include "vector"
6 #include "queue"
7 #include "cmath"
8 #include "string"
9 #include "cctype"
10 #include "map"
11 using namespace std;
12 #define pb push_back
13 #define lc(x) (x << 1)
14 #define rc(x) (x << 1 | 1)
15 #define lowbit(x) (x & (-x))
16 #define ll long long
17 #define maxn 500050
18 int n, k;
19 int loc[maxn], head, tail;
20 ll dp[maxn], val[maxn], dq[maxn], sum[maxn];
21 ll cmp[maxn];
22
23 ll calc2(int a, int b) {
24 return val[a+1] - val[b+1];
25 }
26
27 int main() {
28 int T;
29 scanf("%d", &T);
30 while(T--) {
31 scanf("%d%d", &n, &k);
32 sum[0] = 0, head = tail = 0, dp[0] = 0;
33 loc[tail++] = 0, cmp[0] = 0;
34 for(int i = 1; i <= n; i++) {
35 scanf("%lld", &val[i]);
36 sum[i] = val[i] + sum[i-1];
37 }
38 for(int i = 1; i <= n; i++) {
39 while(head + 1 < tail && (cmp[loc[head+1]] - cmp[loc[head]]) <= i * calc2(loc[head+1], loc[head])) head++;
40 int j = loc[head];
41 dp[i] = dp[j] + sum[i] - sum[j] - (i - j) * val[j+1];
42 cmp[i] = dp[i] - sum[i] + i * val[i+1];
43 if(i + 1 >= 2 * k) {
44 while(head + 1 < tail && (cmp[loc[tail-1]] - cmp[loc[tail-2]]) * calc2(i - k + 1, loc[tail-1]) >= (cmp[i - k + 1] - cmp[loc[tail-1]]) * calc2(loc[tail-1], loc[tail-2])) tail--;
45 loc[tail++] = i - k + 1;
46 }
47 }
48 printf("%lld\n", dp[n]);
49 }
50 return 0;
51 }
52