请问高位大佬,为什么要有q[++t]=0这步啊?
查看原帖
请问高位大佬,为什么要有q[++t]=0这步啊?
709586
lllllluogu楼主2023/9/10 22:39
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int a[N],n,k,q[N];
ll suf[N],f[N];
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i],suf[i]=suf[i-1]+a[i];
	int h=1,t=0;q[++t]=0;
	for(int i=1;i<=n+1;i++){
		while(h<=t&&q[h]<i-k-1)h++;
		f[i]=max(f[i],f[q[h]]+suf[i-1]-suf[q[h]]);
		while(h<=t&&f[q[t]]-suf[q[t]]<f[i]-suf[i])t--;
		q[++t]=i;
	}
	cout<<f[n+1];
}
2023/9/10 22:39
加载中...