60分求条
查看原帖
60分求条
593492
_wronganswer_楼主2024/12/21 17:35
#include<bits/stdc++.h>
#define long lont int
using namespace std;
int n,m,dp[1000005],mx,a[1000005];
deque<int>q;
signed main(){
	cin>>n>>m;
	m++;
	for(int i=1;i<=n;++i)cin>>a[i],mx+=a[i];
	q.push_back(0);
	for(int i=1;i<=n;++i){
		dp[i]=dp[q.front()]+a[i];
	//	cout<<dp[i]<<" ";
		while(!q.empty()&&dp[q.back()]>=dp[i])q.pop_back();
		q.push_back(i);
		if(i-q.front()==m)q.pop_front();
	} 
	int ans=0x3f3f3f3f;
	for(int i=n;i>=n-m+1;i--)ans=min(ans,dp[i]);
	cout<<mx-ans;
}
2024/12/21 17:35
加载中...