前言
单调队列优化动态规划就是字面意思——即由单调队列来优化动态规划的一种方法。
前置知识:
-
动态规划
-
单调队列
例题
P1725 琪露诺
题目简述
给定一长度为 $N+1$ 的数列 $A$ , 第 $1$ 项为 $0$。
以第一项为起点 , 对于当前的位置 $i$
可以转移到: $(i+L,i+R)$ 中任意一位置
并且获得当前位置上数的价值。
则求出当位置 $≥N+1$ 时可以取得的最大价值和。
思路
一道经典的单调队列优化动态规划问题,对于动态规划,首先要定义状态。
我们定义 $dp[i]$ 表示以 $i$ 结尾能获得的最大值,这个应该很好列出来。
然后我们来推状态转移方程。其实这个也很好推,只不过优化的话要动一点脑子。首先我们可以得到:
$$dp[i] = max(dp[j]) + a[i] (i-R \le j \le i-L)$$
解释一下:就是前面能跳到这个格子的格子里面取一个最大值再加上这个格子本身的价值。
但是!我们发现如果暴力地去枚举 $j$ 会超时,那怎么办呢?
注意到每次求最大值的区间的长度是一个固定的长度,在一个固定长度的区间内求最大值,所以我们联想到单调队列。
对于求 $max(dp[j])$ 可以使用单调递减队列求解:
for(int i=L;i<=n;i++){ll res=i-L;while(head<=tail && dp[res]>=dp[q[tail]]) tail--;q[++tail]=res;while(head<=tail && q[head]+R<i) head++;dp[i]=dp[q[head]]+rock[i];if(i+R>n) ans=max(ans,dp[i]);}
然后我们设最后的队头为 $head$,队列为 $q$,那么状态转移方程就变为:
$$dp[i] = dp[q[head]] + a[i]$$
现在就不超时了。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10;
ll rock[N],dp[N],q[N];//dp[i]表示以结尾的最大值
ll n,L,R,head,tail,ans=-1e9;void init(){memset(dp,128,sizeof dp);dp[0]=0;return ;
}
int main(){cin>>n>>L>>R;for(int i=0;i<=n;i++) cin>>rock[i];init();for(int i=L;i<=n;i++){ll res=i-L;while(head<=tail && dp[res]>=dp[q[tail]]) tail--;q[++tail]=res;while(head<=tail && q[head]+R<i) head++;dp[i]=dp[q[head]]+rock[i];if(i+R>n) ans=max(ans,dp[i]);}cout<<ans;return 0;
}
P2034 选择数字
题目简述
给定一行 $n$ 个非负整数 $a_1 ,\cdots, a_n$。现在你可以选择其中若干个数,但不能有超过 $k$ 个连续的数字被选择。你的任务是使得选出的数字的和最大。
对于 $20%$ 的数据,$n \le 10$。
对于另外 $20%$ 的数据,$k=1$。
对于 $60%$ 的数据,$n \le 10^3$。
对于 $100%$ 的数据,$1 \le n \le 10^5$,$1 \le k \le n$,$0 \le $ 数字大小 $ \le 10^9$。
时间限制 $500$ms。
思路
这道题的思路不太好想,个人觉得特别是状态转移。
首先我们定义 $dp[i][0/1]$ 表示第 $i$ 个数选或者不选,这个挺简单。
然后我们来看状态转移。首先如果不选的话就从上一个数选或者不选里面选一个最大值:
$$dp[i][0] = \max(dp[i-1][0],dp[i-1][1])$$
对于选择这个数,由于 $k$ 的存在,我们不能选择连续 $k$ 个数字,所以如果当前的数字选了,那么前面最多选 $k-1$ 个数字。
所以 $i$ 必须由某一个 $j(j \in [i-k,i-1])$ 转化过来,并且 $j$ 不能被选。
我们记录前缀和数组 $sum$,那么转移方程就是:
$$dp[i][1] = max(dp[j][0] + sum[i] - sum[j])(j \in [i-k,i-1])$$
又注意到 $sum[i] - sum[j]$ 可以拆分:
$$dp[i][1] = \max(dp[j][0]-sum[j])+sum[i](j \in [i-k,i-1])$$
这个就是代码的转移方程了,好了我们终于写完了!
记得最后要在选和不选之中取最大值。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
ll dp[N][2];//dp[i]表示第i项选或者不选的最大值
ll num[N],sum[N],q[N];
ll n,k,head,tail;
int main(){cin>>n>>k;for(int i=1;i<=n;i++){cin>>num[i];sum[i]=sum[i-1]+num[i];}for(int i=1;i<=n;i++){dp[i][0]=max(dp[i-1][0],dp[i-1][1]);//更新dp[i][0]while(head<=tail && dp[i][0]-sum[i]>dp[q[tail]][0]-sum[q[tail]]) tail--;q[++tail]=i;while(head<=tail && q[head]+k<i) head++;dp[i][1]=dp[q[head]][0]-sum[q[head]]+sum[i];//更新dp[i][1]}cout<<max(dp[n][0],dp[n][1]);//最终判断return 0;
}