P2627 [USACO11OPEN] Mowing the Lawn G （ [USACO Open11] 修剪草坪/P2034 选择数字 ）题解

P2627 [USACO11OPEN] Mowing the Lawn G

搬运工
单调队列优化DP
简单题，和P2034重了
题意：给定一行 \(n\) 个非负整数 \(a_1 \cdots a_n\)。现在你可以选择其中若干个数，但不能有超过 \(k\) 个连续的数字被选择。你的任务是使得选出的数字的和最大。（直接抄的2034）
正着考虑发现很麻烦，不知道咋维护，但是我们如果考虑删去的话就很有前途，正难则反。
设 \(f_i\) 表示前 \(i\) 个数合法状态的最小删除和，方程 \(f_i=max\{a_t+f_{t-1}\}\)
到 \(i\) 位置时，肯定选出一个位置 \(t\) 的数字删去，\(i-k\le t\le i\)，选完之后，我们还要保证选的 \(t\) 位置之前是合法状态，所以再加上 \(f_{t-1}\)，拿单调队列优化就做完了。

#include<bits/stdc++.h>
#define int long long
inline int read(){
	char ch=getchar();int x=0,f=1;
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
	return x*f;
}
const int N=1e5+10;
int n,k,q[N],e[N],head=1,tail=0,f[N];
signed main(){
	// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
	n=read();k=read();int ans=0;
	for(int i=1;i<=n;++i)e[i]=read(),ans+=e[i];
	for(int i=1;i<=k;++i){
		while(head<=tail&&e[i]<=e[q[tail]])tail--;
		q[++tail]=i;
	}
	for(int i=k+1;i<=n;++i){
		int l=i-k;
		while(head<=tail&&e[i]+f[i-1]<=e[q[tail]]+f[q[tail]-1])tail--;
		q[++tail]=i;
		if(q[head]<l)head++;
		f[i]=e[q[head]]+f[q[head]-1];
	}
	std::cout<<ans-f[n];
}