为什么另外一个过了,这个一直是70分
查看原帖
为什么另外一个过了,这个一直是70分
690320
MoGuYun_12楼主2023/8/5 12:26

单调队列优化 代码:

#include <bits/stdc++.h>

using namespace std;
long long n,k,x,s[100001],dp[100001],t[100001];
int q[100001],head,tail=1;
int main()
{
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++)
	{
	    scanf("%lld",&x);
		s[i]=s[i-1]+x;
	}
	q[0]=0;
	for(int i=1;i<=k;i++)
	{
		dp[i]=s[i];
	}
	for(int i=1;i<=n;i++)
	{
		dp[i]=dp[i-1];
		t[i]=s[i]-dp[i-1];
		if(q[head]<i-k && head<tail)
		{
			head++;
		}
		dp[i]=s[i]-t[q[head]];
		while(t[q[tail-1]]>=t[i] && head<tail)
		{
			tail--;
		}
		q[tail++]=i;
	}
	printf("%lld",dp[n]);
	return 0;
}

请大佬帮忙看一下哪里有问题,谢谢!

2023/8/5 12:26
加载中...