求助单调队列dp板子
  • 板块P1725 琪露诺
  • 楼主abc_de
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/9/2 22:36
  • 上次更新2023/10/27 12:46:33
查看原帖
求助单调队列dp板子
287395
abc_de楼主2022/9/2 22:36

wa两个测试点 80pts 求dalao帮忙看看 谢谢

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int n,l,r;
int w[maxn];
int dp[maxn],ans=-0x3f3f3f3f;
struct node{
	int p,a;	
}q[maxn];
int rd(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();	
	}
	return x*f;
}
int main(){
//	freopen("A.in","r",stdin);
//	freopen("A.out","w",stdout);
	n=rd();l=rd();r=rd();
	for(int i=0;i<=n;i++) w[i]=rd();
	int l1=0,r1=0;
	for(int i=1;i<=n+r;i++) dp[i]=-0x3f3f3f3f;
	for(int i=l;i<=n+r;i++){
		while(l1<=r1&&q[r1].p>i-l) r1--;
		while(l1<=r1&&q[l1].p<i-r) l1++;
		dp[i]=q[l1].a+w[i];
		while(l1<=r1&&dp[i-l+1]>q[r1].a) r1--;
		q[++r1].a=dp[i-l+1];
		q[r1].p=i-l+1;
	}
	for(int i=n+1;i<=n+r;i++) ans=max(ans,dp[i]);
	cout<<ans;
	return 0;	
}
2022/9/2 22:36
加载中...