Mowing the Lawn G「单调队列优化DP」

题目描述

在一年前赢得了小镇的最佳草坪比赛后，Farm John变得很懒，再也没有修剪过草坪。现在，新一轮的最佳草坪比赛又开始了，Farm John希望能够再次夺冠。

然而，Farm John的草坪非常脏乱，因此，Farm John只能够让他的奶牛来完成这项工作。Farm John有(N)((1 <= N <= 100,000))只排成一排的奶牛，编号为(1...N)。每只奶牛的效率是不同的，奶牛i的效率为(E_i)((0 <= E_i <= 1,000,000,000))。

靠近的奶牛们很熟悉，因此，如果Farm John安排超过(K)只连续的奶牛，那么，这些奶牛就会罢工去开派对:)。因此，现在Farm John需要你的帮助，计算FJ可以得到的最大效率，并且该方案中没有连续的超过(K)只奶牛。

输入格式

第一行：空格隔开的两个整数 (N) 和 (K)

第二到 (N+1) 行：第 (i+1) 行有一个整数 (E_i)

输出格式

第一行：一个值，表示 Farm John 可以得到的最大的效率值

输入输出样例

输入 #1

输出 #1

思路分析

首先不难想到，每只奶牛在当前选或者不选都有可能对后续的最佳答案产生影响，所以我们在转移时完全可以将这两个状态分开来存，即开一个二维的(f)数组。
另外像这种需要连续选物品的(DP)，使用前缀和数组会有奇效
定义(f[i][0/1])数组表示到第i头牛，状态为(0/1)的情况，(0)表示不选，(1)表示选。那么两种状态的转移方程就可以得出：
- 对于不选的情况，我们直接从上一个转移即可，即：(f[i][0] = max(f[i-1][1],f[i-1][0]))。
- 选了的情况相对复杂，我们让当前这头牛为一连串牛的结尾，遍历起点，则有：(f[i][1] = max(f[i][1],f[j-1][0]+sum[i]-sum[j-1]));
~~信心满满的交上去，70分T掉~~
显然，这样的转移方程在一串牛的长度很长时时间效率会很低，所以考虑优化
仔细看一看(f[i][1])的这个转移方程，我们是以(i)为终点寻找一个最优起点，那最最优的起点应该有两条性质：
1. 效率值大
2. 位置靠后(这样才可以形成更长的序列)
根据上面的性质，对于一些两个都不符合的点，显然就没有机会再选了，要想对后面的情况产生贡献，最起码得占一个，显然要用单调队列来维护，这也是单调队列的核心思想：人家比你小还比你强，凭什么选你
根据上面的转移方程，因为(sum[i])是定值，所以用队列维护(f[j-1][0]-sum[j-1])就可以了（别把前缀和丢了）

Code

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 100010
#define ll long long
using namespace std;
inline ll read(){
	ll x = 0,f = 1;
	char ch =getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x * f;
}
ll n,k;
ll f[N][2],e[N],sum[N],q[N];
int main(){
	n = read(),k = read();
	for(int i = 1;i <= n;i++){
		e[i] = read();
		sum[i] = sum[i-1] + e[i];
	}
	int head = 0,tail = 1;//注意队首为0，要不你会默认最开始1不选是最优的
	q[tail] = 1;
	f[1][1] = e[1];
	for(int i = 2;i <= n;i++){
		while(head<=tail && i-q[head] > k)head++;
		f[i][1] = f[q[head]][0] + sum[i] - sum[q[head]];//既然在队首没被弹掉，肯定是最大的啦
		f[i][0] = max(f[i-1][0],f[i-1][1]);//这个直接转移就行
		while(head<=tail && f[i][0]-sum[i]>=f[q[tail]][0]-sum[q[tail]])tail--;
		q[++tail] = i;
	}
	printf("%lld
",max(f[n][0],f[n][1]));
	return 0;
}