如果真的要枚举,排序暴力硬做的话肯定会挂掉
那么就是要优化的,显然划分一个2c的序列,答案不回比划分两个c的更优
可以画个图证明一下
而划分成小于c的序列,就相当于划分成一堆1的序列
划分成c-2c的序列呢?显然是不如划分成c和另外一个,肯定不会更差
这样的话就检查划分成c和1就可以解决了
#include<cstdio>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<algorithm>
#include<queue>
#define int long long
using namespace std;
template<class T>inline void read(T &x)
{
x=0;register char c=getchar();register bool f=0;
while(!isdigit(c))f^=c=='-',c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
if(f)x=-x;
}
template<class T>inline void print(T x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar('0'+x%10);
}
int n,c;
int a[10000001];
deque<int> q;
int mi[1000001];
int f[1000001];
int sum[1000001];
signed main(){
read(n);read(c);
for(int i=1;i<=n;++i){
read(a[i]);
sum[i]=sum[i-1]+a[i];
}
memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;++i){
while(!q.empty()&&q.front()+c<=i){
q.pop_front();
}
while(!q.empty()&&a[q.back()]>=a[i]){
q.pop_back();
}
q.push_back(i);
mi[i]=a[q.front()];
}
f[0]=0;
for(int i=1;i<=n;++i){
f[i]=f[i-1]+a[i];
if(i>=c){
f[i]=min(f[i],f[i-c]+sum[i]-sum[i-c]-mi[i]);
}
}
cout<<f[n];
return 0;
}