传送门
Solution:
既然是删掉k/c个，那么k<c是不删除的无意义，k=c删除1个，c<=k<2c还是删除1个，那么相当于第c+1个到第k个放在上一区间是无意义的。证明：假如前c个的最小值是mini ，如果
a[c+1]<mini，那么删掉的就是a[c+1]，不值得，如果a[c+1]>=mini，那么删除的还是mini，把c+1个划分到上个区间也是无意义的。
但如果长度为2c的话就能删除2个，但一定不如化成2个c长度的区间优秀。假如前c个的最小值是mini1，次小值是mini2，后c个的最小值是mini3，假如mini2<mini3，那么删除
mini1+mini3>mini1+mini2，划分成2段更好，如果mini2>=mini3，那么删除的还是mini1+mini3，是等价的。
这样我们就能想到区间dp了，f[i]为到i位置能减去的最大的和是多少，可以从f[i-1]转移过来，就相当于把i分到一个长度不到c的区间里，无法减去值，也可以从f[i-c]转移过来，说明吧i-
c+1到i分成一个长度为c的区间，然后删掉里面的最小值
分析到这儿我们发现其实就是一个RMQ+dp 对于RMQ 这道题可以用单调队列来解决 当然 st表，线段树也是可以的
友情提示：用stl的deque会炸哦~
/*1、维护区间最值； 2、去除冗杂状态； 3、保持队列单调（最大值是单调递减序列，最小值是单调递增序列）； 4、最优选择在队首 */ #include<bits/stdc++.h> using namespace std; typedef long long ll; int n,c; ll a[100005],sum,b[100005],dp[100005]; ll q[100005]; int main() { cin>>n>>c; c=min(c,n+1); for(int i=1;i<=n;i++) { cin>>a[i]; sum+=a[i]; } int head,tail; q[head=tail=1]=1; for(int i=2;i<=c-1;i++) { while(a[q[tail]]>=a[i]) { tail--; } q[++tail]=i; } for(int i=c;i<=n;i++) { while(head<=tail&&q[head]<=i-c) head++; while(head<=tail&&a[q[tail]]>=a[i]) tail--; q[++tail]=i; b[i]=a[q[head]]; } for(int i=c;i<=n;i++) dp[i]=max(dp[i-1],dp[i-c]+b[i]); cout<<sum-dp[n]; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9461512.html
