0x59 单调队列优化 DP

在0x11节讲解“栈”和0x12节讲解“队列”时，我们已经引入了“单调栈”和“单调队列”两种思想。它们的本质都是借助单调性，及时排除不可能的决策，保持候选集合的高度有效性和秩序性。请读者仔细回顾0x12节“最大子序和”这道例题，该问题的答案可以形式化表述为：

此处的 $i$ 非常类似于动态规划的“状态”， $j$ 则类似于动态规划的“决策”。我们从小到大枚举每个 $i \in [1, N]$ ，当 $i$ 增大 1 时， $j$ 的取值范围 $[i - M, i - 1]$ 的上、下界同时增大 1，变为 $[i - M + 1, i]$ 。这意味着不仅有一个新的决策 $j = i$ 进入了候选集合，也应该把过时的决策 $j = i - M$ 从候选集合中排除。单调队列非常适合优化这种决策取值范围的上、下界均单调变化，每个决策在候选集合中插入或删除至多一次的问题。

类比“最大子序和”一题的思想，请读者尝试解答下面几道例题。

【例题】Fence POJ1821

有 $N$ 块木板从左到右排成一行，有 $M$ 个工匠对这些木板进行粉刷，每块木板至多被粉刷一次。第 $i$ 个工匠要么不粉刷，要么粉刷包含木板 $S_{i}$ 的、长度不超过 $L_{i}$ 的连续的一段木板，每粉刷一块可以得到 $P_{i}$ 的报酬。求如何安排能使工匠们获得的总报酬最多。 $1 \leq N \leq 16000, 1 \leq M \leq 100$ 。

先把所有工匠按照 $S_{i}$ 排序，这样一来，每个工匠粉刷的木板一定在上一个工匠粉刷的木板之后，使我们能够按顺序进行线性DP。

设 $F[i,j]$ 表示安排前 $i$ 个工匠粉刷前 $j$ 块木板（可以有空着不刷的木板），工匠们能获得的最多报酬。

1. 第 $i$ 个工匠可以什么也不刷，此时 $F[i,j] = F[i - 1,j]$ 。

2. 第 $j$ 块木板可以空着不刷，此时 $F[i,j] = F[i,j - 1]$ 。

3. 第 $i$ 个工匠粉刷第 $k + 1$ 块到第 $j$ 块木板。根据题意，该工匠粉刷总数不能超过 $L_{i}$ ，且必须粉刷 $S_{i}$ ，所以需要满足： $k + 1 \leq S_{i} \leq j$ 并且 $j - k \leq L_{i}$ 。于是，有状态转移方程：

我们重点来看这个方程如何优化。首先，我们多次提到，在考虑内层循环 $j$ 以及决策 $k$ 时，可把外层循环变量 $i$ 看作定值。这样一来，状态转移方程中的各项可分为两部分：

1. $P_{i} * j$ ，除定值 $i$ 外，只有状态变量 $j$ 。

2. $F[i - 1,k] - P_{i} * k$ ，除定值 $i$ 外，只有决策变量 $k$ 。

状态转移方程可改写为：

当 $j$ 增大时， $k$ 的取值范围上界 $S_{i} - 1$ 不变，下界 $j - L_{i}$ 变大。按与“最大子序和”一题类似的想法，我们比较一下任意两个决策 $k_{1}$ 和 $k_{2}$ 。不妨设 $k_{1} < k_{2} \leq S_{i} - 1$ 。

因为 $k_{2}$ 比 $k_{1}$ 更靠后，所以随着 $j$ 的增加， $k_{1}$ 会比 $k_{2}$ 更早从范围 $[j - L_{i}, S_{i} - 1]$ 中被排除。如果还满足 $F[i - 1, k_{1}] - P_{i} * k_{1} \leq F[i - 1, k_{2}] - P_{i} * k_{2}$ ，那么就意味着 $k_{2}$ 不但比 $k_{1}$ 更优，还比 $k_{1}$ 的存活时间更长。在这种情况下， $k_{1}$ 就是一个无用的决策，应该被直接排除出候选集合。

综上所述，我们可以维护一个决策点 $k$ 单调递增，数值 $F[i - 1,k] - P_{i} * k$ 单调递减的队列。只有这个队列中的决策才有可能在某一时刻成为最优决策。这个单调队列支持如下几种操作：

1. 当 $j$ 变大时，检查队头元素，把小于 $j - L_{i}$ 的决策出队。

2. 需要查询最优决策时，队头即为所求。

3. 有一个新的决策要加入候选集合时，在队尾检查 $F[i - 1, k] - P_i * k$ 的单调性，把无用决策从队尾直接出队，最后把新决策加入队列。

在本题中具体来说，当内层循环开始时 $(j = S_{i})$ ，建立一个空的单调队列，把 $\left[\max (S_i - L_i,0),S_i - 1\right]$ 中的决策依次加入候选集合(执行操作3)。对于每个 $j = S_{i}\sim N,$ 先在队头检查决策合法性（操作1)，然后取队头为最优决策（操作2）进行状态转移。因为每个决策至多入队、出队一次，故转移的时间复杂度均摊O(1)。整个算法的时间复杂度为O(NM)。

struct rec{ int L, P, S; } a[110];
int n, m;
int f[110][16010], q[16010];
bool operator <(rec a, rec b) {
    return a.S < b.S;
}
int calc(int i, int k) {
    return f[i - 1][k] - a[i].P * k;
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &a[i].L, &a[i].P, &a[i].S);
        sort(a + 1, a + m + 1);
        for (int i = 1; i <= m; i++) {
            // 初始化单调队列
            int l = 1, r = 0;
            // 把最初的候选集合插入队列
            for (int k = max(0, a[i].S - a[i].L); k <= a[i].S - 1; k++) {
                // 插入新决策，维护队尾单调性
                while (l <= r && calc(i, q[r]) <= calc(i, k)) r--;
                q[++r] = k;
            }
        }
    for (int j = 1; j <= n; j++) {
        // 不粉刷时的转移
        f[i][j] = max(f[i - 1][j], f[i][j - 1]);
        // 粉刷第 k+1~j 块木板时的转移
        if (j >= a[i].S) {
            // 排除队头不合法决策
            while (l <= r && q[l] < j - a[i].L) l++;
            // 队列非空时，取队头进行状态转移
            if (l <= r) f[i][j] = max(f[i][j],
                     calc(i, q[l]) + a[i].P * j);
        }
    }
}

}cout<<f[m][n]<<end1;

*【例题】Cut the Sequence FOJ3017

给定一个长度为 $N$ 的序列 $A$ ，要求把该序列分成若干段，在满足“每段中所有数的和”不超过 $M$ 的前提下，让“每段中所有数的最大值”之和最小。试计算这个最小值。 $N \leq 10^{5}$ ，数列 $A$ 中的数非负，且不超过 $10^{6}$ ， $M \leq 10^{11}$ 。

设 $F[i]$ 表示把前 $i$ 个数分成若干段，在满足每段中所有数的和不超过 $M$ 的前提下，各段的最大值之和最小是多少。容易写出状态转移方程：

若采用枚举决策 $j$ 的方法，时间复杂度为 $O(N^{2})$ 。然而，该方程似乎很难进行优化，因为 $\max_{j+1 \leq k \leq i} \{A_k\}$ 不容易用一个简单的多项式来表示，不容易找到单调性。我们曾多次强调，DP 转移优化的指导思想就是及时排除不可能的决策，保持候选集合的高度有效性和秩序性。本着这个原则，我们考虑一个决策 $j$ 何时是必要的。

引理：

在上述方程中，若 $j(0 \leq j < i)$ 可能成为最优决策，则除了 $\sum_{k = j + 1}^{i} A_{k} \leq M$ 外，必然还满足以下两个条件之一：

1. $A_{j} = \max_{j\leq k\leq i}\{A_{k}\}$

2. $\sum_{k = j}^{i}A_{k} > M$ （即 $j$ 是满足 $\sum_{k = j + 1}^{i}A_{k}\leq M$ 的最小的 $j)$

证明：

反证法。假设两个条件都不满足，即 $A_{j} < \max_{j\leq k\leq i}\{A_{k}\}$ 并且 $\sum_{k = j}^{i}A_{k}\leq M$ 。由此可知 $\max_{j\leq k\leq i}\{A_k\} = \max_{j + 1\leq k\leq i}\{A_k\}$ 。另外， $F$ 数组显然具有单调性，即 $F[j - 1]\leq F[j]$ （多一个数，答案肯定更大）。于是：

上式的含义就是决策 $j - 1$ 比 $j$ 更优。而决策的取值范围是 $0 \leq j < i, j - 1$ 比 $j$ 更容易满足这个条件。所以，上式与 $j$ 可能成为最优决策矛盾，故假设不成立。

证毕。

引理中的第2个条件比较简单，只需预处理出对于每个 $i$ ，满足 $\sum_{k = j + 1}^{i}A_{k}\leq M$ 的最小的 $j$ ，记为 $C[i]$ 。在计算 $F[i]$ 时，从 $C[i]$ 进行一次转移即可。下面我们单独讨论满足引理中第1个条件的决策 $j$ 的维护方法。

根据引理，当一个新的决策 $j_{2}$ 插入候选集合时，若候选集合中已有的决策 $j_{1}$ 满

足条件 $j_{1} < j_{2}$ 并且 $A_{j_1}\leq A_{j_2}$ ，则 $j_{1}$ 就是无用决策，可被排除。

综上所述，我们可以维护一个决策点 $j$ 单调递增、数值 $A_{j}$ 单调递减的队列，只有该队列中的元素才可能成为最优决策。

与上一道题目不同的是，该队列只是一个 $A_{j}$ 单调递减的队列，关于转移方程等式右边的 $F[j] + \max_{j+1 \leq k \leq i} \{A_{k}\}$ 并没有单调性。所以我们不能简单地取队头为最优决策，而是要再加一个额外的数据结构（例如二叉堆）。二叉堆与单调队列保存相同的候选集合，该插入时一起插入，该删除时一起删除（或用“懒惰删除法”，参见0x71节），只不过单调队列以 $A_{j}$ 递减作为比较大小的依据，二叉堆以 $F[j] + \max_{j+1 \leq k \leq i} \{A_{k}\}$ 作为比较大小的依据，保证能快速在候选集合中查询最值。事实上，我们一般称这种做法为“二叉堆与单调队列建立了映射关系”。

最后，关于 $\max_{j+1 \leq k \leq i} \{A_k\}$ 的计算有两种方法。第一种是按照区间最值问题，直接用ST算法预处理，支持O(1)查询。第二种是仔细发掘本题中单调队列的性质，我们可以发现，队列中某一项的 $\max_{j+1 \leq k \leq i} \{A_k\}$ 的结果其实就是队列中下一个元素的 $A$ 值。

在整个算法中，每个 $j$ 至多在单调队列和二叉堆中插入和删除一次，故时间复杂度为 $O(N \log N)$ 。

单调队列优化多重背包

在0x52节“背包”中，我们已经介绍了多重背包问题的朴素解法和二进制拆分解法。若使用单调队列，可以把求解多重背包问题的复杂度进一步优化到 $O(NM)$ 。先来回顾一下多重背包问题的模型：

给定 $N$ 种物品，其中第 $i$ 种物品的体积为 $V_{i}$ ，价值为 $W_{i}$ ，并且有 $C_{i}$ 个。有一容积为 $M$ 的背包，要求选择若干个物品放入背包，使得物品总体积不超过 $M$ 的前提下，物品的价值总和最大。

在0x52节背包的解法中，DP数组省略了“阶段”这一维。当外层循环进行到 $i$ 时， $F[j]$ 表示从前 $i$ 种物品中选出若干个放入背包，体积之和为 $j$ 时，价值之和最大是多少。倒序循环 $j$ ，在状态转移时，考虑选取第 $i$ 个物品的个数 cnt:

画出能够转移到状态 $j$ 的决策候选集合 $\{j - cnt * V_i \mid 1 \leq cnt \leq C_i\}$ :

当循环变量 $j$ 减小1时：

可以发现，相邻两个状态 $j$ 和 $j - 1$ 对应的决策候选集合没有重叠，很难快速地从 $j - 1$ 对应的集合得到 $j$ 对应的集合。

但是，我们试着考虑一下状态 $j$ 和 $j - V_{i}$

这两者对应的决策候选集合之间的关系，与我们前面讲解的单调队列题目非常相似，只有一个新决策加入候选集合、一个已有决策被排除。所以，我们应该把状态 $j$ 按照除以 $V_{i}$ 的余数分组，对每一组分别进行计算，不同组之间的状态在阶段 $i$ 不会互相转移：

余数为0— $0,V_{i},2V_{i},\dots$

余数为1— $1,1 + V_{i},1 + 2V_{i},\dots$

···

余数为 $V_{i} - 1$ —— $(V_{i} - 1), (V_{i} - 1) + V_{i}, (V_{i} - 1) + 2V_{i}, \dots$

把“倒序循环 $j$ ”的过程，改为对每个余数 $u\in [0,V_i - 1]$ ，倒序循环 $p = \lfloor (M - u) / V_i\rfloor \sim 0$ ，对应的状态就是 $j = u + p*V_{i}$ 。第 $i$ 种物品只有 $C_i$ 个，故能转移到 $j = u + p*V_{i}$ 的决策候选集合就是 $\{u + k*V_i\mid p - C_i\leq k\leq p - 1\}$ 。写出新的状态转移方程①：

与本节的“Fence”一题类似，把外层循环 $i$ 和 $u$ 看作定值，当内层循环变量 $p$ 减小1时，决策 $k$ 的取值范围 $[p - C_i, p - 1]$ 的上、下界均单调减小。状态转移方程等号右侧的式子仍然分为两部分，仅包含变量 $p$ 的 $p * W_i$ 和仅包含变量 $k$ 的 $F[u + k * V_i] - k * W_i$ 。综上所述，我们可以建立一个决策点 $k$ 单调递减、数值 $F[u + k * V_i] - k * W_i$ 单调递减的队列，用于维护候选集合。对于每个 $p$ ，执行单调队列的三个惯例操作：

1. 检查队头合法性，把大于 $p - 1$ 的决策点出队。

2. 取队头为最优决策，更新 $F[u + p * V_i]$ 。

3. 把新决策 $k = p - C_{i} - 1$ 插入队尾，入队前检查队尾单调性，排除无用决策。

整个算法的时间复杂度为 $O(NM)$ 。

int calc(int i, int u, int k) {
return f[u + k*v[i]] - k*w[i];
}
int main()
{
cin >> n >> m;
memset(f, 0xfc, sizeof(f)); // -INF
f[0] = 0;
// 物品种类
for (int i = 1; i <= n; i++) {
scanf("%d%d%d", &V[i], &W[i], &C[i]);
// 除以V[i]的余数
for (int u = 0; u < V[i]; u++) {
// 建立单调队列
int l = 1, r = 0;
// 把最初的候选集合插入队列
int maxp = (m - u) / V[i];
for (int k = maxp-1; k >= max(maxp-C[i], 0); k--)
while (l <= r && calc(i, u, q[r]) <= calc(i, u, k)) r--;
q[++r] = k;
}
// 倒序循环每个状态
for (int p = maxp; p >= 0; p--) {
// 排除过时决策
while (l <= r && q[l] > p - 1) l++;
// 取队头进行状态转移
if (l <= r)
f[u + p*v[i]] = max(f[u + p*v[i]], calc(i, u, q[l]) + p*w[i]);
// 插入新决策，同时维护队尾单调性
if (p - C[i] - 1 >= 0) {
while (l <= r && calc(i, u, q[r]) <= calc(i, u, p-C[i] - 1)) r--;
q[++r] = p - C[i] - 1;
}
}

int ans  $= 0$  for (int  $\mathbf{i} = 1$  .i  $\Leftarrow$  m; i++) ans  $=$  max(ans,f[i]); cout << ans << endl;

最后，我们对单调队列优化DP的模型进行总结。我们重新写出上面三道例题的状态转移方程：

只关注“状态变量”“决策变量”及其所在的维度，这些状态转移方程都可以大致归为如下形式（除第三个方程稍有不同）：

上式所代表的问题覆盖范围广泛，是DP中一类非常基本、非常重要的模型。这种模型也被称为1D/1D的动态规划。它是一个最优化问题， $L(i)$ 和 $R(i)$ 是关于变量 $i$ 的一次函数，限制了决策 $j$ 的取值范围，并保证其上下界变化具有单调性。val(i,j) 是一个关于变量 $i$ 和 $j$ 的多项式函数，通常是决定我们采用何种优化策略的关键之处。

回想本节三道例题的解法，我们都把 $val(i,j)$ 分成了两部分，第一部分仅与 $i$ 有关，第二部分仅与 $j$ 有关。对于每个 $i$ ，无论采取哪个 $j$ 作为最优决策，第一部分的值都是相等的，可以在选出最优决策更新 $F[i]$ 时再进行计算、累加。而当 $i$ 发生变化时，第二部分的值不会发生变化，从而保证原来较优的决策，在 $i$ 改变后仍然较优，不会产生乱序的现象。于是，我们就可以在队列中维护第二部分的单调性，及时排除不可能的决策，让DP算法得以高效进行。所以，在上述模型中，多项式 $val(i,j)$ 的每一项仅与 $i$ 和 $j$ 中的一个有关，是使用单调队列进行优化的基本条件。