题解区的用单调队列实现的没有,只有手打队列的,但他的马蜂太奇怪了看不懂,求大佬看看思路哪里错了
#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课还没讲,要等好几天才讲