题意略。
这个题目我开始题意理解得有点问题。本题的实质是在这个数列中选择一些数字，使得选出的这些数字之和最大，用dp来解。
我们先要明确：当我选择数列长度为2 * c时，不如把这个长度为2 * c的劈成两个c，这样对答案的贡献更大一些。
定义dp[i]为我在[i,n]中可谋取的最大贡献。
dp[i] = max{dp[k]} + earn[i,i + c - 1] (i + c <= k <= n - c - 1)。
可用单调队列优化。
详见代码：
#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
typedef long long LL; LL ai[maxn],dp[maxn];
LL st[maxn][],mm[maxn];
int que[maxn],head,tail,n,c; void init(){
mm[] = -;
for(int i = ;i < maxn;++i){
mm[i] = (i & (i - )) == ? mm[i - ] + : mm[i - ];
}
}
void init_rmq(){
for(int i = ;i <= n;++i) st[i][] = ai[i];
for(int j = ;j <= mm[n];++j){
for(int i = ;i + (<<j) - <= n;++i){
st[i][j] = min(st[i][j - ],st[i + (<<(j - ))][j - ]);
}
}
}
LL rmq(int l,int r){
LL k = mm[r - l + ];
return min(st[l][k],st[r - (<<k) + ][k]);
} int main(){
init();
while(scanf("%d%d",&n,&c) == ){
LL sum = ;
for(int i = ;i <= n;++i){
scanf("%lld",&ai[i]);
sum += ai[i];
}
init_rmq();
memset(dp,,sizeof(dp));
head = tail = ;
LL ans = ;
for(int i = n - c + ;i >= ;--i){
dp[i] = dp[que[head]] + rmq(i,i + c - );
ans = max(ans,dp[i]);
while(head < tail && dp[que[tail - ]] < dp[i + c - ]) --tail;
que[tail++] = i + c - ;
}
printf("%lld\n",sum - ans);
}
return ;
}