lilns @ 2018-10-03 08:01:10
#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
long long qr[maxn],q[maxn],sum[maxn],dp[maxn],e[maxn];
int l=0,r=0,n,k;
int qu(int x)
{
while(l<=r&&qr[l]<x-k)
{
l++;
}
int d=dp[x-1]-sum[x];
while(l<=r&&d>=q[r])
{
r--;
}
q[++r]=d;
qr[r]=x;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&e[i]);
sum[i]=sum[i-1]+e[i];
}
for(int i=1;i<=n;i++)
{
qu(i);
dp[i]=q[l]+sum[i];
}
cout<<dp[n];
return 0;
}
这里q存的d值,qr存的加入这个点在原数列的位置, 同学用q存位置,d【i】存i位置的值就ac了,不明白两者之间的问题和差距,求解。。。。