求助sd夏令营的一个DP队列优化题目
  • 板块灌水区
  • 楼主CuSO4_and_5H2O
  • 当前回复22
  • 已保存回复22
  • 发布时间2022/7/17 09:52
  • 上次更新2023/10/27 19:55:56
查看原帖
求助sd夏令营的一个DP队列优化题目
231946
CuSO4_and_5H2O楼主2022/7/17 09:52

题解区的用单调队列实现的没有,只有手打队列的,但他的马蜂太奇怪了看不懂,求大佬看看思路哪里错了

#include<bits/stdc++.h>
#define int long long
using namespace std;

deque<int> q;
int n,k,a[1008600],f[1000086],Max=10000860;

signed main(){
	cin>>n>>k;
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		sum+=a[i];
		f[i]=a[i];
		if(!q.empty() && i>k)
			f[i]+=f[q.front()];
		if(!q.empty() && i-q.front()>k) q.pop_front();
		while(!q.empty() && f[q.back()]>=f[i]) q.pop_back();
		q.push_back(i);
	}
	for(int i=n-k;i<=n;i++)
		Max=min(f[i],Max);
	cout<<sum-Max;
}

顺便一说,这是那个下午最简单的题目了,并且课程表上写的是单调队列单调栈st表但是最简单的例题是DP(DP课还没讲,要等好几天才讲

2022/7/17 09:52
加载中...