单调队列优化

Vision271 · 2022-07-21 22:49:08 · 个人记录

概述

单调队列

单调队列是满足以下条件的特殊双端队列：
- 队列中存储下标。
- 队列元素（下标）严格单调递增（当然递减也可以）。
- 队列元素（下标）实际对应的、一种关系到转移的要素严格单调递减（注意是严格，相等是不行的）。

单调队列优化

对转移式形如 dp_i=\min/\max_{j=?}^{i-1} \ dp_j+\dots 的 dp，可以使用单调队列优化其转移。
- 可以看到，其核心特点在于任意一个点是由其前面的连续一段值决定的。
- 更进一步地，是由那一段中某个最满足某种/某几种条件的一个点决定的，决策具备单调性。
- 从而有一种保存一系列“有效转移点”的思路，除他们之外的任意点作为转移的出发点都是不划算的。
之所以这些点满足单调队列条件，是因为：
- (1)优点优于劣点；
- (2)可能会存在优点过期而要使用相对较劣的点来转移的情况。这句话的隐语是说，劣点的过期时间更晚，也就是下标更大。
综上，点与点之间有如下关系：
- 一个点“严格优于另一个点”。即他首先再转以上优，然后下标大。这种情况下，他应当将严格劣于他的点全部清除。
- 如果仅仅是优，那么他应该在队头。应当尽量用他转移；但过期早的也是他。
- 相应的，仅仅是过期晚但劣的点，应当在队列较靠后的位置。
- 而严格劣的点，“组织不需要他们”。
那么就可以使用一般的单调队列优化。

实现原理

For(i,1,n){
    while(hd<=tl && q[hd]<i-k) ++hd;//k是长度限制。
//注意，这里是i-k，因为i可以获得一个所谓的长为“k”的跨度转移过来，这个跨度是不包含转移起始点的。当然，我们要就实际情况讨论。
    dp[i]=dp[q[hd]]+(particular check);
    while(hd<=tl && (particular check) --tl;
    q[++tl]=i;
}

代码解释：
- 第一行：判断队列中的点是否已经过期。如果队头点已经过期，不再可以用于转移，那么弹出。
- 第二行：转移出当前点的 dp 值。
- 第三行：进行判断。判断是否存在队尾点严格劣于新点，将他们清除。
- 第四行：加入新点。此时他是至高无上的，一定可以加入（因为他是过期最晚的）。
需要特别声明的是，请注意设计好初始状态。前几个点实质上是由 dp_0，或者叫什么都好，转移来的。

例题

P5202 [USACO19JAN]Redistricting P

题意：
- 给定一个长为 N 的字符串 S，由 H 与 G 组成。
- 给定一个最大长度 k，要求将 S 划分为任意个长度不大于 k 的段.
- 设法使其中 cnt_G\geqslant cnt_H 的段数尽量少。输出这个最小值。
显然可以设计 DP：
- 状态设计：dp_i，表示 1\sim i 至少分出多少个不满足题意（下称为非法）的区间。
- 状态转移方程：dp_i=\min_{j=i-k}^{i-1} (dp_j+(cnt_G\geqslant cnt_h))。
其中 cnt_G\geqslant cnt_H 可以由前缀和的方式实现，譬如令 H=1,G=-1，于是转移时的 \Delta=[sum_i-sum_j\leqslant 0]。
于是转移逻辑就变成按以下关键字排优先度：
- 1.非法区间尽量少。
- 2.非法区间一样多，所拥有的 sum 尽量小（这样更容易转移出优先度更高的点）。
到这里已经比较显然了，我放核心代码吧。

For(i,1,n){
    while(hd<=tl && q[hd]<i-k) ++hd;
    dp[i]=dp[q[hd]]+(sum[i]-sum[q[hd]]<=0);
    while(hd<=tl && (dp[q[tl]]>dp[i] || (dp[q[tl]]==dp[i] && sum[i]<sum[q[tl]]) ) ) --tl;
    q[++tl]=i;
}

单调队列优化多重背包

仔细观察多重背包的转移式。
不妨令 dp_{i,j} 表示考虑完毕前 i 种物品，已付出 j 的代价的最大价值（同构状态问题暂不考虑，视情况而定），则转移式如下：

dp_{i,j}=\max_{k=0}^{num_i} (dp_{i-1,j-k\times c_i}+k\times w_i)

观察到一个明显的性质：关于 c_i 的各个剩余系相互独立。
故考虑分剩余系转移。对每个剩余系，我们使用一种特化的单调队列优化：
- 我们来考察 dp_{i,j} 的转移来源。能否对他们做一个单调队列？
- 队头弹出部分：较为容易。
  - 若 j'+c_i\times num_i<j，则其过期，弹出。这里 j' 是转移来源 dp_{i-1,j'} 的下标。
- 单调性，转移和队尾弹出怎么办？
- 发现主要难度在后面的 k\times w_i 上。这使得队列内的元素不是静态的。怎么办？
- 法一.即时计算偏移：
  - 首先进一步丰富队列内元素所包含的信息。现在队列内元素是一个三元组 (j',v,id)，v=dp_{i-1,j'}，id 是 j' 在该剩余系中的编号，或者说为 \frac{j}{c_i}+1。
  - 这里的 v，我们称为单调队列内元素的初始转移效果。相应地，称 rv 为实际转移效果，即 v+\frac{j-j'}{c_i}\times w_i。idn-id=\frac{j-j'}{c_i}。
- 法二.总体偏移：
  - 引入一个概念“总体偏移”：在该剩余系中每向右移动一个，也即 j+=c_i，相当于给队内所有元素统一加 w_i。
  - 故维护一个总体偏移量 delta，记当前所在剩余系为 rest，则 delta=\dfrac{j-rest}{c_i}。
  - 元素入队时，入队的 v 应当为 dp_{i-1,j}-delta。相应地，记 dp_{i-1,j} 为 rv。
  - 至用它的时候，队内元素 +delta 就是转移结果。
  - 似乎常数相对较小。
- 还有一个小 tip：这里的队尾弹出和队尾插入是在转移之前进行的。
  - 这是因为可以此类物品一个都不选转移过来，转移来源是早就处理好的上一层。
  - 作为对比，一般单调队列的转移来源是同层的，自己转自己是没有道理的，而且会导致入队的元素尚未被转移出来。
综上所述，可以通过此种方式将多重背包的复杂度优化到 O(n\min(\sum c,\sum v))。
给出一段示范代码（代码中的实现方式为即时计算偏移）：

int n;
struct goods{
    int c,w,num;
}a[maxn];
int dp[maxn][maxn];
int sum[maxn];
struct from{
    int k,v,id;//k 是实际的 ∑c，v 是 dp 值，id 是剩余系下编号 
    from(){}
    from(int _k,int _v,int _id){k=_k,v=_v,id=_id;}
}q[maxn];
int hd,tl;

il void DP(){
    int rg; q[0].k=-inf;//目的是总是能在 hd=0 时 ++hd。通过控制 id 来把 tl 减成负的显然不明智，那会导致 q[0] 有值。
    For(i,1,n){
        rg=a[i].c*a[i].num; sum[i]=sum[i-1]+rg; if(sum[i]>uselim) sum[i]=uselim;
        for(int j=0;j<a[i].c;++j){
            for(int k=j,idn=0;k<=sum[i];k+=a[i].c,++idn){
                while(hd<=tl && q[hd].k+rg<k) ++hd;
                while(hd<=tl && q[tl].v+(idn-q[tl].id)*a[i].w<=dp[i-1][k]) --tl;
                q[++tl]=from(k,dp[i-1][k],idn);

                dp[i][k]=q[hd].v+(idn-q[hd].id)*a[i].w;
            }
            hd=tl=0;
        }
        For(j,1,uselim) chkmax(dp[i][j],dp[i][j-1]);
    }
}

这是一道题的代码搬过来了，所以有一些小东西：
- 其中 uselim 是询问的 lim 的上界。
- 最后的 chkmax 是题目需要，正常情况下可以不要。