本文共 946 字，大约阅读时间需要 3 分钟。

定义$f[i]$表示前$i$头奶牛不选第$i$头奶牛的最大收益

那么$f[i]=\max \{$

其中$j\in [i-k-2,i-1]$

发现$su{m}_{i-1}$固定,求的是$f[j]-su{m}_j$的最小值

这个可以用线段树处理,但是没有必要

求最小值只需要维护一段区间长度为$k+1$的单调队列即可

#include 
   
    using namespace std;#define int long longconst int maxn = 1e6+10;int f[maxn],sum[maxn],n,k,e[maxn];int head = 1, tail = 0, q[maxn];//单调队列 signed main(){
   	cin >> n >> k;	for(int i=1;i<=n;i++)	scanf("%lld",&e[i] );	for(int i=1;i<=n+1;i++)	sum[i] = sum[i-1]+e[i] ;	q[++tail] = 0;	//f[i]可以从距离自己距离0,1,2,3,4,5,6,7,8,9.....k的位置转移而来 	for(int i=1;i<=n+1;i++)	{
   		while( q[tail]-q[head]+1>k+1 )	head++;		int las = q[head];		f[i] = f[las]-sum[las]+sum[i-1];		while( tail>=head && f[i]-sum[i]>=f[q[tail]]-sum[q[tail]] )	tail--;		q[++tail] = i;	}	printf("%lld",f[n+1] );	}
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/116258010 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！