Lisa

删边似乎挨个删复杂度也不会高到离谱

毕竟也就是$O(2*n)$的事。，因为显然可以想到先删点权最大的点，然后拓扑排序缩点啥的来一波

但是也可以从边的考虑，每一条边只会被删一次，且应会是在删两边较大的那个点的点权的时候被删，这样从边的视角考虑就省事了。

#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;
}