动态规划中的单调队列优化
最近经常遇到单调队列结构以及基于斜率的优化方法的题目。听到身边的许多大牛都完成了这些题型后,我也感到压力很大,只能尽力跟上进度。建议从基础开始深入学习单调队列相关知识。
什么类型的DP需要用到常规的单调队列？
类似这样的转移方程可以用到单调队列：
其中，g[j]是一个与i无关系的数。w[i]只与i有关系。
怎么用？
为了进行动态规划操作，我们首先初始化一个双端队列（deque）。在动态规划的过程中：
1）在操作过程中，在双端队列中删除超出范围的第一个元素；
2）使用前一个位置的状态值来进行更新；
3）然后将当前计算出的数值与双端队列中的最后一个元素进行比较；
4）如果最后一个元素的价值低于当前计算出的数值，则需要从双端队列中删除最后一个元素；
5）继续这一过程直至双端队列为空或者找到一个更优的位置插入当前数值；
6）最后将该数值添加到双端对尾位置。
原因
1、该单调队列中的元素全部处于指定的范围内。
2、此轮次中队首元素最优（若非如此，则会很快被后续轮次取代）。
3、为何不同时维护多个候选者？因为初始候选者往往较为落后（一旦超出范围即被淘汰）。
例题 JZOJ 1771. 【NOIP动态规划专题】烽火传递
Problem Description
面对单调队列的问题时通常会遇到较为简单的题目。
将变量f[i]定义为当i被选中时所需的最小代价。
初始状态设定如下：f[0]=0；对于其他位置i=1到n来说，f[i]=∞。
其中j必须满足\text{max}(0, i-m) \leq j < i。
为何如此限定？若允许j超出此限制，则可能导致某些区间不符合条件从而出现错误。正确的设定需确保这些区间无间隙。
最终答案可通过在区间n-m+1\leq i\leq n内寻找最小值来确定。
该算法的时间复杂度为O(nm).
没有单调队列的代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define I_O(x) freopen(""#x".in","r",stdin);freopen(""#x".out","w",stdout)
int n,m;
int w[100001];
int f[100001];
int main()
{
I_O(beacon);
scanf("%d%d",&n,&m);
int i,j;
for (i=1;i<=n;++i)
scanf("%d",&w[i]);
memset(f,127,sizeof f);
f[0]=0;
for (i=1;i<m;++i)
{
for (j=0;j<i;++j)//分两段写的原因是为了卡常——你也可以并在一起，然后j的初值为max(0,i-m)
f[i]=min(f[i],f[j]);
f[i]+=w[i];
}
for (i=m;i<=n;++i)
{
for (j=i-m;j<i;++j)
f[i]=min(f[i],f[j]);
f[i]+=w[i];
}
int ans=0x7f7f7f7f;
for (i=n-m+1;i<=n;++i)
ans=min(ans,f[i]);
printf("%d\n",ans);
}经过分析发现，该方程利用单调队列即可实现。通过在算法中存储并维护最优决策点（即最优解），从而使得时间复杂度得以从O(nm)降低到O(n)。
正解代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define I_O(x) freopen(""#x".in","r",stdin);freopen(""#x".out","w",stdout)
int n,m;
int w[100001];
int que[100001],head=0,tail=0;
int f[100001];
int main()
{
I_O(beacon);
scanf("%d%d",&n,&m);
int i,j;
for (i=1;i<=n;++i)
scanf("%d",&w[i]);
memset(f,127,sizeof f);
f[0]=0;
que[0]=0;
for (i=1;i<=n;++i)
{
if (que[head]<i-m)
++head;//将超出范围的队头删掉
f[i]=f[que[head]]+w[i];//转移（用队头）
while (head<=tail && f[que[tail]]>f[i])
--tail;//将不比它优的全部删掉
que[++tail]=i;//将它加进队尾
}
int ans=0x7f7f7f7f;
for (i=n-m+1;i<=n;++i)
ans=min(ans,f[i]);
printf("%d\n",ans);
}