C++(g++ 7.5.0) 解法, 执行用时: 22ms, 内存消耗: 1812K, 提交时间: 2022-11-23 10:20:33

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int len,k;
ll dp[N],a[N];
deque<int> q;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>len>>k;
    ll s=0;
    for(int i=1;i<=len;i++) cin>>a[i],s+=a[i];
    for(int i=1;i<=len;i++){
        if(!q.empty()&&q.front()<=i-k) q.pop_front();
        while(!q.empty()&&a[i]<=a[q.back()]){
            q.pop_back();
        }
        q.push_back(i);
        dp[i]=dp[i-1];
        if(i>=k){
            dp[i]=max(dp[i],dp[i-k]+a[q.front()]);
        }
    }
    cout<<s-dp[len];
}

C++(clang++ 11.0.1) 解法, 执行用时: 39ms, 内存消耗: 1416K, 提交时间: 2022-10-12 16:52:20

#include<bits/stdc++.h>
using namespace std ;
const int N = 1e5 + 5 ;
#define ll long long
int n,c ;
int a[N],q[N] ;
ll f[N] ;
int main()
{
	cin>>n>>c ;
	ll sum=0 ;
	for(int i=1;i<=n;++i) cin>>a[i],sum+=a[i] ;
	f[0]=0 ;
	int l=1,r=0 ;
	for(int i=1;i<=n;++i)
	{
		while(l<=r&&i-q[l]>=c) l++ ;
		while(l<=r&&a[i]<=a[q[r]]) r-- ;
		q[++r]=i ;
		if(i>=c) f[i]=max(f[i-1],f[i-c]+a[q[l]]) ;
        else f[i]=f[i-1] ;
	}
	cout<<sum-f[n]<<'\n' ;
	return 0 ;
}