求助(0分)
  • 板块P1725 琪露诺
  • 楼主ycy1124
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/6/6 13:37
  • 上次更新2024/6/6 17:54:16
查看原帖
求助(0分)
1199534
ycy1124楼主2024/6/6 13:37
#include<bits/stdc++.h>
using namespace std;
int a[200005],dp[200005];
struct Node{
	int w,i;
};
deque<Node>p;//zhu,bei
int main(){
	int n,l,r;
	scanf("%d%d%d",&n,&l,&r);
	for(int i=0;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=0;i<=n+1;i++){
		if(!p.empty()&&p.back().i<i-l){
			p.pop_back();
		}
		if(p.empty()){
			dp[i]=a[i];
		}
		else{
			dp[i]=a[i]+p.back().w;
		}
		if(i-l+1>=1){
			while(!p.empty()&&dp[i-l]>=p.front().w){
				p.pop_front();
			}
			p.push_front({dp[i-l],i});
		}
	}
	for(int i=0;i<=n+1;i++){
		printf("%d ",dp[i]);	
	}
	return 0;
}
2024/6/6 13:37
加载中...