Codeforces 940E Cashback

题意：一共给你N个数，然后将他们分成连续的子集，每个集合可以删除元素个数/c 个最小元素，然后求每个集合删除元素后的总和。

题解：我们将集合分为1个元素或者K个元素，每K个元素查询一下最小值，然后找到最小值，然后 dp一下就可以找到最后的结果

emmm，当时CF的时候题意读错了，没有注意到连续，也没有注意到每K个只删除一个（我以为是删除所有的最小元素），然后今天补题的时候发现了要连续， WA了一发看了数据，才发现只删除一个，不是删除全部最小。。。

代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define LL long long
 4 #define ULL unsigned LL
 5 #define fi first
 6 #define se second
 7 #define lson l,m,rt<<1
 8 #define rson m+1,r,rt<<1|1
 9 #define max3(a,b,c) max(a,max(b,c))
10 const int INF = 0x3f3f3f3f;
11 const LL mod = 1e9+7;
12 typedef pair<int,int> pll;
13 const int N = 1e5+10;
14 LL sum[N<<2], Min[N<<2];
15 LL dp[N], a[N];
16 void PushUp(int rt){
17     sum[rt] = sum[rt<<1] + sum[rt<<1|1];
18     Min[rt] = min(Min[rt<<1], Min[rt<<1|1]);
19 }
20 void Build(int l, int r, int rt){
21     if(l == r){
22         sum[rt] = a[l];
23         Min[rt] = sum[rt];
24         return ;
25     }
26     int m = l+r >> 1;
27     Build(lson);
28     Build(rson);
29     PushUp(rt);
30 }
31 LL Minn = 0;
32 LL Query(int L, int R, int l, int r, int rt){
33     if(L <= l && r <= R){
34         if(Minn > Min[rt]) Minn = Min[rt];
35         return sum[rt];
36     }
37     LL ans = 0;
38     int m = l+r >> 1;
39     if(L <= m) ans += Query(L,R,lson);
40     if(m < R)  ans += Query(L,R,rson);
41     return ans;
42 }
43 int main(){
44     int n, c;
45     scanf("%d%d",&n,&c);
46     for(int i = 1; i <= n; i++) scanf("%I64d", &a[i]);
47     Build(1,n,1);
48     for(int i = 1; i <= n; i++){
49         if(i >= c){
50             Minn = 1e10;
51             LL tmp = Query(i-c+1,i,1,n,1);
52             dp[i] = min(dp[i-1]+a[i], dp[i-c] + tmp - Minn);
53         }
54         else dp[i] = dp[i-1] + a[i];
55     }
56     printf("%I64d
", dp[n]);
57     return 0;
58 }