MnZn求助,以AC但不理解
  • 板块P2034 选择数字
  • 楼主jikky
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/9/29 15:11
  • 上次更新2024/9/29 19:26:02
查看原帖
MnZn求助,以AC但不理解
1382982
jikky楼主2024/9/29 15:11
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int l,r;
long long  f[N][2];
long long  sum[N];
int x;
long long q[N];
int main(){
	int n;
	cin>>n;
	int k;
	cin>>k;
	r=0;
	l=1;
	for(int i=1;i<=n;i++){
		cin>>x;
		sum[i]=sum[i-1]+x;
	}
	for(int i=1;i<=n;i++){
		f[i][0]=max(f[i-1][0],f[i-1][1]);
		while(q[l]<i-k&&l<=r){
		    l++;
		}
		f[i][1]=f[q[l]][0]-sum[q[l]]+sum[i];
		if(l>r){
			r++;
			q[r]=i;
		}
		else{
			while(l<=r&&f[i][0]-sum[i]>f[q[r]][0]-sum[q[r]]) {
			   r--;
		    }
		    r++;
		    q[r]=i;
		}
	}
	cout<<max(f[n][0],f[n][1]);
	return 0;
}

为什么把r的初值改为1就过了

2024/9/29 15:11
加载中...