单调队列优化DP
题目
在一年前赢得了小镇的最佳草坪比赛后,FJ 变得很懒,再也没有修剪过草坪。
现在,新一轮的最佳草坪比赛又开始了,FJ 希望能够再次夺冠。
然而,FJ 的草坪非常脏乱,因此,FJ 只能够让他的奶牛来完成这项工作。
FJ 有 N 只排成一排的奶牛,编号为 1 到 N。
每只奶牛的效率是不同的,奶牛 i 的效率为 Ei。
编号相邻的奶牛们很熟悉,如果 FJ 安排超过 K 只编号连续的奶牛,那么这些奶牛就会罢工去开派对。
因此,现在 FJ 需要你的帮助,找到最合理的安排方案并计算 FJ 可以得到的最大效率。
注意,方案需满足不能包含超过 K 只编号连续的奶牛。
输入格式
第一行:空格隔开的两个整数 N 和 K;
第二到 N+1 行:第 i+1 行有一个整数 Ei。
输出格式
共一行,包含一个数值,表示 FJ 可以得到的最大的效率值。
数据范围
1≤N≤105,
0≤Ei≤109
输入样例:
5 2
1
2
3
4
5
输出样例:
12
样例解释
FJ 有 5 只奶牛,效率分别为 1、2、3、4、5。
FJ 希望选取的奶牛效率总和最大,但是他不能选取超过 2 只连续的奶牛。
因此可以选择第三只以外的其他奶牛,总的效率为 1 + 2 + 4 + 5 = 12。
思路
分析图示
状态表示: f[i]
表示从前i
头牛中选,且合法的所有方案集合中的最大效率值
状态计算:
对于每头牛i来说,有选和不选两种方案。
不选第i
头牛 , f[i] = f[i-1]
;
选第i
头牛,又可以按照连续长度划分为:长度为1
,长度为2
,长度为3
,,,,,,,长度为k
当我们所选的连续长度为j
时 (1<=j<=k)
,所选的牛可以是
注意第i-j
头牛不选,因为我们所选的牛连续长度为j
,选了连续长度就大于j
了。
故选择第i
头牛方程为: f[i]= f[i-j-1]+s[i]-s[i-j]
将选择第i
头牛的方程进行转换
状态计算方程为: f[i]=max(f[i-1],g[i-j]+s[i])
(1<=j<=k)
考虑优化:
最大值依赖于g[i-j]
,因此定义一个长度为k
的单调递减的队列维护g[i-j]
,使得队头的g[i-j]
最大,每次更新答案时取出队头进行更新。 1<=j<=k
,其实就是在求长度为k的滑动窗口的最大值。
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=1e5+10;
LL f[N];
LL s[N];
int q[N]; //数组模拟队列,队列中存放的是下标
LL g(int i)
{
if(i==0) return 0;
return f[i-1]-s[i];
}
int main()
{
int n,k;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&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++; //超出滑动窗口,出队列 ,此时s[i]还没入队,因此取不到等于号
f[i]=max(f[i-1],g(q[hh])+s[i]);
while(hh<=tt&&g(q[tt])<=g(i)) tt--; //维护一个单调递减队列,队头元素最大
q[++tt]=i;
}
printf("%lld\n",f[n]);
return 0;
}
原来i-j位置不选啊
if(q[hh]<i-k) hh++; //超出滑动窗口,出队列 ,此时s[i]还没入队,因此取不到等于号
这句话有问题可以用
priority_queue<int>
来做优先队列吗单调队列和优先队列不一样呀
可以用priority_queue[HTML_REMOVED]来做吗
为什么tt要从0开始取呢,当i=j的时候,g[0]=f[-1]-s[0]表示的是什么含义呢
用了deque而非数组模拟队列,这有啥问题嘛?WA了QAQ
明明推导出来的式子里有j,落实到代码上j就不见了,不能理解
j=q[hh]
啊,就是离i符合要求的m个范围内的式子 :f[j−1]−s[j]可以获得最大值时的j,放入q[hh]中了当时不明白,现在理解了,感谢你!
老哥,你提高课刷了几遍,每次都能看到你在评论区
真清楚,明白
细节处理的很棒
最后一张图有问题
应该是抄错了 导致后面都乱了
Orz
这个写得很清楚 Orz
大佬,能解释下$f[i]= f[i-j-1]+s[i]-s[i-j]$,为什么这样就包括所有长度为$1$到$j$的所有情况了,求教啊
$s$是前缀和. 式子只包含$j$, $j$范围$1$到$k$. 而我们用的是单调队列维护$i$前面$i-k到i-1$之间一共$k$个数里面的$f[i-j-1] - s[i-j]$的最大值, 所以能同时覆盖j所处在的$1$到$k$范围