单调队列 , 零分 , 求助
查看原帖
单调队列 , 零分 , 求助
180059
return_dirt楼主2020/10/28 22:56

过样例了,然而全WA

#include <cstdio>
#include <algorithm>
using namespace std;
 
 
int n,l,r; 
int line[300000];
int dp[300000],a[300000];
int ans;

int main()
{
	scanf("%d%d%d",&n,&l,&r);
	for(int i=0;i<=n;i++)
	{
		scanf("%d",&a[i]);
		dp[i]=a[i];
	}
	int end=0;
	int head=0;

	for(int i=l;i<=n;i++)
	{
		while(line[head+1]<i+l-r&&head<end)head++;
		while(end!=head&&dp[i]>dp[line[end]])end--;
		line[++end]=i;
		for(int j=head+1;j<=end;j++)
		dp[i+l]=max(dp[i]+a[i+l],dp[i+l]);
	}

	for(int i=n-r+1;i<=n;i++)
    ans=max(ans,dp[i]);
	printf("%d",ans);
	return 0;
} 
2020/10/28 22:56
加载中...