修建草坪 单调队列优化DP

题目:

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

然而,FJ 的草坪非常脏乱,因此,FJ 只能够让他的奶牛来完成这项工作。FJ 有 N 只排成一排的奶牛,编号为 1 到 N。每只奶牛的效率是不同的,奶牛 i 的效率为 Ei 。

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

思路:

状态表示:

f [ i ] f[i] f[i]表示从前i个里面选,满足条件的最大效率

状态转移方程:

f [ i ] = m a x ( f [ i − 1 ] , f [ i − j − 1 ] + s [ i ] − s [ i − j ] ) , 1 ≤ j ≤ k f[i] = max(f[i-1],f[i-j-1]+s[i]-s[i-j]),1 \leq j \leq k f[i]=max(f[i−1],f[i−j−1]+s[i]−s[i−j]),1≤j≤k
不选第i个对应 f [ i − 1 ] f[i-1] f[i−1],选第i个对应 f [ i − j − 1 ] + s [ i ] − s [ i − j ] f[i-j-1]+s[i]-s[i-j] f[i−j−1]+s[i]−s[i−j]
s [ i ] s[i] s[i]固定,而 f [ i − j − 1 ] − s [ i − j ] f[i-j-1]-s[i-j] f[i−j−1]−s[i−j]的最大值可以使用单调队列进行优化,注意开long long
注意:使用单调队列需要进行初始化

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
ll s[N];
ll f[N],q[N];
int n,k;

ll g(int i)
{
	return f[i-1] - s[i];
}
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>s[i];
		s[i] += s[i-1];
	}
	int hh=0,tt=0;
	for(int i=1;i<=n;i++)
	{
		if(q[hh] < i-k) hh++;
		f[i] = max(f[i-1],g(q[hh])+s[i]);
		while(hh<=tt && g(q[tt]) <= g(i)) tt--;
		q[++tt] = i;
	}
	cout<<f[n]<<'\n';
	return 0;
}
上一篇:P3580 [POI2014]ZAL-Freight(单调队列dp)


下一篇:BZOJ 2442: [Usaco2011 Open]修剪草坪 单调队列