20pts求助,stl单调队列
查看原帖
20pts求助,stl单调队列
372336
一个句号楼主2023/8/30 07:34
#include<iostream>
#include<deque>
using namespace std;
#define ll long long 
const int N=100005;
/*
  dp[i]表示选i头奶牛时能获得的最大效率
  在i-k到i中必定有一断点j
  断开后,dp[i]=dp[j-1]+a[j+1]+a[j+2]+...+a[i]
  即为dp[i]=dp[j-1]+sum[i]-sum[j];
  
  sum[i]为定值,移动一下,选取dp[j-1]-sum[j]的最大值
  dp[i]往左滑动选取最大dp[j]
  别忘了初始化
 */

ll n,k,ans;//最多安排k只连续奶牛,是单调队列的窗口
ll e[N],sum[N];
ll dp[N],t[N];
deque<ll>q;

int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>e[i];
		sum[i]=sum[i-1]+e[i];
	}
	q.push_back(0);
	for(int i=1;i<=n;i++){
		while(!q.empty()&&dp[i]>=dp[q.back()-1]-sum[q.back()]+sum[i]){
			q.pop_back();
		}
		q.push_back(i); 
		while(!q.empty()&&i-k>q.front()){
			q.pop_front();
		}
		dp[i]=dp[q.front()-1]-sum[q.front()]+sum[i];
	}

	cout<<dp[n];
	return 0;
}

2023/8/30 07:34
加载中...