求助大佬,这个为什么只能AC一半啊
  • 板块P1725 琪露诺
  • 楼主ShuF
  • 当前回复5
  • 已保存回复5
  • 发布时间2024/4/14 17:38
  • 上次更新2024/4/14 20:48:59
查看原帖
求助大佬,这个为什么只能AC一半啊
1291751
ShuF楼主2024/4/14 17:38
#include<bits/stdc++.h>
using namespace std;

int N,L,R;
int f[20005];int num[20005];
struct PII{
	int num;int time;
};
deque<PII> dq;
void go_in(int n,int i){
	PII t;
	if(!dq.empty()){
		if(dq.front().time<i-R+1) dq.pop_front();
	}
	while(!dq.empty() && dq.back().num <= n) dq.pop_back();
	t.num=n;t.time=i;dq.push_back(t);
}

void solve(){
	int ans=-1e8;
	cin>>N>>L>>R;
	for(int i=0;i<=N;i++){
		cin>>num[i];
	}
	
	memset(f, 0x80, sizeof(f));
	
	f[0]=0;

	for(int i=L;i<=N;i++){//L前的位置无法到达,默认为负无穷
	    go_in(f[i-L],i-L);//求l时,l只能由0过来,所以推出来每次入队列是i-L
	    int from=dq.front().time;//最大的数据

		f[i]=f[from]+num[i];

		if(i+R > N ) ans=max(ans,f[i]);		
	}
	cout<<ans<<endl;
	
}

int main(){
	solve();
}
2024/4/14 17:38
加载中...