单调队列优化
代码:
#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;
}
请大佬帮忙看一下哪里有问题,谢谢!