[Acwing] 1087. 修剪草坪 单调队列dp

前言

传送门 :

思路

集合表示 : f [ i ] f[i] f[i] 表示从前 i i i头牛,并且合法的最大价值

对于当前第 i i i头牛来考虑 :

• 不选,那么可以直接从 f [ i − 1 ] f[i-1] f[i−1]转移过来
• 选, 那么肯定不能连续选,所以我们将 i i i前面分为几个小段
  [ i − j + 1 , i ] , [ i − j + 2 , i ] . . . . . [i-j+1,i],[i-j+2,i]..... [i−j+1,i],[i−j+2,i].....

因此状态计算为 :
f [ i ] = m a x ( f [ i − 1 ] , f [ i − j − 1 ] + s [ i ] − s [ i − j ] ) f[i] = max(f[i-1],f[i-j-1]+s[i] - s[i-j]) f[i]=max(f[i−1],f[i−j−1]+s[i]−s[i−j])

我们可以将右边化简为 :
f [ i − j − 1 ] − s [ i − j ] + s [ i ] = g ( i − j ) + s [ i ] f[i-j-1] - s[i-j] +s[i] = g(i-j)+s[i] f[i−j−1]−s[i−j]+s[i]=g(i−j)+s[i]

为了使价值最大我们应该使得 m a x ( g ( i − j ) ) max(g(i-j)) max(g(i−j)) 因此我们可以使用一个滑动窗口

维护一个长度为 k k k区间的最大值

code

const int N  = 1e5+10;
ll f[N],s[N];
int q[N],a[N];
ll g(int i){
	if(i == 0)
	return 0;
	return f[i-1] - s[i];
}
void solve()
{
	int n,k;cin>>n>>k;
	for(int i=1;i>a[i];
		s[i] = s[i-1]+a[i];
	}
	
	int hh = 0 , tt = 0 ;
	
	for(int i=1;i