蒟蒻求助
查看原帖
蒟蒻求助
333574
Tyyyyyy楼主2021/4/6 13:53
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,k;
ll dp[110000],sum[110000],e[110000];
struct node
{
	int pos;
	ll val;
}q[110000];
node push(ll nv,int np)
{
	node a;
	a.pos=np;
	a.val=nv;
	return a;
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&e[i]);
		sum[i]=sum[i-1]+e[i];
	}
	int head=1,tail=1;
	dp[k]=sum[k];
	q[head]=push(dp[k-2]-sum[k-1],k);
	for(int i=k+1;i<=n;i++)
	{
		while(head<=tail&&q[tail].val<=dp[i-2]-sum[i-1])tail--;
        q[++tail]=push(dp[i-2]-sum[i-1],i);
        while(i-q[head].pos>=k)head++;
        dp[i]=max(dp[i-1],sum[i]+q[head].val);
	}
	printf("%lld",dp[n]);
	return 0;
}
/*dp[i]=max( max{sum[i]-sum[j-1]+dp[j-2]}(i-k+1<=j<=i) , dp[i-1] )
	相当于是找(dp[j-2]-sum[j-1])的最大值。 
*/
2021/4/6 13:53
加载中...