2018.09.10【BZOJ2442】修剪草坪（單調隊列優化DP）

傳送門

解析：

首先狀态轉移還是比較好想的。

令 f i , 0 / 1 f_{i,0/1} fi,0/1​表示考慮前 i i i個時，選擇第 i i i個與不選第 i i i個能夠獲得的最大效益。

我們維護一個 s u m sum sum數組表示字首和。

那麼，狀态轉移方程也就呼之欲出了

f i , 0 = m a x ( f i − 1 , 0 , f i − 1 , 1 ) f_{i,0}=max(f_{i-1,0},f_{i-1,1}) fi,0​=max(fi−1,0​,fi−1,1​)

f i , 1 = m a x ( f j , 0 − s u m j ) + s u m i ( i − k &lt; = j &lt; i ) f_{i,1}=max(f_{j,0}-sum_j)+sum_i(i-k&lt;=j&lt;i) fi,1​=max(fj,0​−sumj​)+sumi​(i−k<=j<i)

顯然可以使用單調隊列優化。

代碼：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define re register
#define gc getchar
#define pc putchar
#define cs const
#define st static

inline
ll getint(){
	re ll num=0;
	re char c;
	while(!isdigit(c=gc()));
	while(isdigit(c))num=(num<<1)+(num<<3)+(c^48),c=gc();
	return num;
}

int n,k;
ll sum[100002];
ll f[100002][2];
ll q[100002];
int head=1,tail=1;

signed main(){
	n=getint();
	k=getint();
	for(int re i=1;i<=n;++i)sum[i]=sum[i-1]+getint();
	
	for(int re i=1;i<=n;++i){
		f[i][0]=max(f[i-1][0],f[i-1][1]);
		while(q[head]<i-k&&head<=tail)++head;
		f[i][1]=f[q[head]][0]-sum[q[head]]+sum[i];
		while(f[i][0]-sum[i]>f[q[tail]][0]-sum[q[tail]]&&tail>=head)--tail;
		q[++tail]=i;
	}
	
	cout<<max(f[n][0],f[n][1]);
	return 0;
}