Since you are the best Wraith King, Nizhniy Magazin «Mir» at the centre of Vinnytsia is offering you a discount.
You are given an array a of length n and an integer c.
The value of some array b of length k is the sum of its elements except for the 
smallest. For example, the value of the array [3, 1, 6, 5, 2] with c = 2 is 3 + 6 + 5 = 14.
Among all possible partitions of a into contiguous subarrays output the smallest possible sum of the values of these subarrays.
The first line contains integers n and c (1 ≤ n, c ≤ 100 000).
The second line contains n integers ai (1 ≤ ai ≤ 109) — elements of a.
Output a single integer — the smallest possible sum of values of these subarrays of some partition of a.
3 5
1 2 3
6
12 10
1 1 10 10 10 10 10 10 9 10 10 10
92
7 2
2 3 6 4 5 7 1
17
8 4
1 3 4 5 5 3 4 1
23
In the first example any partition yields 6 as the sum.
In the second example one of the optimal partitions is [1, 1], [10, 10, 10, 10, 10, 10, 9, 10, 10, 10] with the values 2 and 90 respectively.
In the third example one of the optimal partitions is [2, 3], [6, 4, 5, 7], [1] with the values 3, 13 and 1 respectively.
In the fourth example one of the optimal partitions is [1], [3, 4, 5, 5, 3, 4], [1] with the values 1, 21 and 1 respectively.
思路：
首先可以证明出最优方案中一定存在所有划分的块的元素量都不大于c。假设最优方案中存在大于c的块，规模为d，d % c = k， d / c = m， k不为0时，额外加入的这k个元素并不会使得当前块被砍掉的元素数量增多，也不会使被砍掉的元素增大，因此把这k个元素独立出来不会使结果变差；当k等于0时，即d是c的m倍时，合并m个规模为c的块不会使总共被砍掉的m个元素便大，相反可能变小。
因此，我们考虑dp，dp[i]表示前i个元素可以被砍掉的最大和，则只需讨论目前最后一个（即第i个）元素是否被取到即可，被取到时，dp[i] = dp[i - c] + min(a[i - c + 1...i]);没被取到时，dp[i] = dp[i - 1]。其中求最小值可以用线段树维护。复杂度O(nlog(n))。
1 #include <iostream> 2 #include <fstream> 3 #include <sstream> 4 #include <cstdlib> 5 #include <cstdio> 6 #include <cmath> 7 #include <string> 8 #include <cstring> 9 #include <algorithm> 10 #include <queue> 11 #include <stack> 12 #include <vector> 13 #include <set> 14 #include <map> 15 #include <list> 16 #include <iomanip> 17 #include <cctype> 18 #include <cassert> 19 #include <bitset> 20 #include <ctime> 21 22 using namespace std; 23 24 #define pau system("pause") 25 #define ll long long 26 #define pii pair<int, int> 27 #define pb push_back 28 #define mp make_pair 29 #define clr(a, x) memset(a, x, sizeof(a)) 30 31 const double pi = acos(-1.0); 32 const int INF = 0x3f3f3f3f; 33 const int MOD = 1e9 + 7; 34 const double EPS = 1e-9; 35 36 /* 37 #include <ext/pb_ds/assoc_container.hpp> 38 #include <ext/pb_ds/tree_policy.hpp> 39 40 using namespace __gnu_pbds; 41 tree<pli, null_type, greater<pli>, rb_tree_tag, tree_order_statistics_node_update> T; 42 */ 43 44 int mi[400015], n, c; 45 ll sum; 46 void pushup(int i) { 47 mi[i] = min(mi[i << 1], mi[i << 1 | 1]); 48 } 49 void build(int i, int l, int r) { 50 if (l == r) { 51 scanf("%d", &mi[i]); 52 sum += mi[i]; 53 return; 54 } 55 int mi = l + r >> 1; 56 build(i << 1, l, mi); 57 build(i << 1 | 1, mi + 1, r); 58 pushup(i); 59 } 60 int query(int i, int l, int r, int x, int y) { 61 if (x <= l && r <= y) { 62 return mi[i]; 63 } 64 int mi = l + r >> 1; 65 int res1 = MOD, res2 = MOD; 66 if (x <= mi) res1 = query(i << 1, l, mi, x, y); 67 if (mi < y) res2 = query(i << 1 | 1, mi + 1, r, x, y); 68 return min(res1, res2); 69 } 70 ll dp[100015]; 71 int main() { 72 scanf("%d%d", &n, &c); 73 build(1, 1, n); 74 for (int i = c; i <= n; ++i) { 75 int res = query(1, 1, n, i - c + 1, i); 76 dp[i] = max(dp[i - 1], dp[i - c] + res); 77 } 78 printf("%lld", sum - dp[n]); 79 return 0; 80 }