【題意】：給出一個長度為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