单调栈优化

相关题目：

• 「Luogu P1886」滑动窗口
• 「NOI2005」瑰丽华尔兹
• 「SCOI2010」股票交易

---

1 引入

前置知识：单调队列、单调栈。

单调队列主要用于维护两端指针单调不减的区间最值，而单调栈则主要用于维护前/后第一个大于/小于当前值的数。

Attention

• 求最小值要维护 单调递增/不减 的单调队列/单调栈，反之亦然。
• 维护单调递增/递减比较时用 小于等于/大于等于，维护单调不减/不增比较时用 小于/大于。

2 单调队列优化具体步骤

• 加入所需元素：向单调队列重复加入元素直到当前元素达到所求区间的右边界，这样就能保证所需元素都在单调队列中。
• 弹出越界队首：单调队列本质上是维护的是所有已插入元素的最值，但我们想要的往往是一个区间最值。于是我们弹出在左边界外的元素，以保证单调队列中的元素都在所求区间中。
• 获取最值：直接取队首作为答案即可。

3 单调栈优化具体步骤

• 弹出非法栈顶：通过比较当前元素与栈顶的大小，弹出不满足单调栈性质的栈顶。以单调递增的栈（即栈顶最大，维护最小值）为例，将所有大于等于当前元素的栈内元素全部弹出。
• 加入当前元素：将当前元素入栈即可。

4 单调队列优化多重背包

Question

你有 $n$ 个物品，每个物品重量为 $w_i$，价值为 $v_i$，数量为 $k_i$。你有一个承重上限为 $W$ 的背包，现在要求你在不超过重量上限的情况下选取价值和尽可能大的物品放入背包。求最大价值。

不了解背包 DP 的请先阅读 [背包 DP](https://leetcode.com/problems/背包 DP/)。设 $f_{i,j}$ 表示前 $i$ 个物品装入承重为 $j$ 的背包的最大价值，朴素的转移方程为

$$f_{i,j}=\underset{k=0}{\overset{k_i}{\max }}(f_{i-1,j-k\times w_i}+v_i\times k)$$

时间复杂度 $O(W\sum k_i)$。

考虑优化 $f_i$ 的转移。为方便表述，设 $g_{x,y}=f_{i,x\times w_i+y},g_{x,y}^{\prime }=f_{i-1,x\times w_i+y}$，其中 $0\le y<w_i$，则转移方程可以表示为：

$$g_{x,y}=\underset{k=0}{\overset{k_i}{\max }}(g_{x-k,y}^{\prime }+v_i\times k)$$

Note

这里的 $g_{x,y}$ 中的 xy，实际上是把原来的 $f_{i,j}$ 按照 $j=x\times w_i+y$ 的方式进行了变形，含义是以该物品的重量 $w_i$ 为基数表示总重量 j 的坐标，如: 物品重量为 10, 则 j=16 时，xy 坐标为 (1,6)。

设 $G_{x,y}=g_{x,y}^{\prime }-v_i\times x$。则方程可以表示为：

$$g_{x,y}=\underset{k=0}{\overset{k_i}{\max }}(G_{x-k,y})+v_i\times x$$

这样就转化为一个经典的单调队列优化形式了。$G_{x,y}$ 可以 $O(1)$ 计算，因此对于固定的 $y$，我们可以在 $O\left(\lfloor \frac{W}{w_i}\rfloor \right)$ 的时间内计算出 $g_{x,y}$。因此求出所有 $g_{x,y}$ 的复杂度为 $O\left(\lfloor \frac{W}{w_i}\rfloor \right)\times O(w_i)=O(W)$。这样转移的总复杂度就降为 $O(nW)$。

Note

解释下这里为什么是一个单调队列（或者说滑动窗口可能更熟悉）。 当我们固定 y，按照 $x=0,1,2,\dots$ 的顺序计算时：

• 计算 $g_{0,y}$：需要 $\max \{G_{0,y}\}$（边界处理）
• 计算 $g_{1,y}$：需要 $\max \{G_{1,y},G_{0,y}\}$
• 计算 $g_{2,y}$：需要 $\max \{G_{2,y},G_{1,y},G_{2,y}\}$
• $⋮$ （共 $\lfloor \frac{W}{w_i}\rfloor$ 个） 所以为了得到最终的 $g_{x,y}$，这里就可以仅通过 $\lfloor \frac{W}{w_i}\rfloor$ 次平移窗口（维护一个大小为 k 的单调队列）得到 $g_{0,y}$ 至 $g_{x,y}$。而 y 的取值是 $0\le y<w_i$ ，所以需要维护 $w_i$ 个这样的单调队列，因此求出所有 $g_{x,y}$ 的复杂度为 $O\left(\lfloor \frac{W}{w_i}\rfloor \right)\times O(w_i)=O(W)$，即用 $O(W)$ 的复杂度就求出了 $f_{i,0},...,f_{i,W}$, 而朴素解法里需要的复杂度是 $O(W\ast k_i)$, 这就是单调队列优化效率高的本质原因。外层循环次数为 n，所以总复杂度就为 $O(nW)$。

Note

朴素解法的本质是求 $f_{i,0},...,f_{i,W}$ 时，每个 $f_{i,j}(0\le j\le W)$ 都会和 $k_i$ 个状态比较大小以取最值，这就导致复杂度为 $O(W\ast k_i)$. 单调队列优化法的本质是将 $f_{i,0},...,f_{i,W}$ 分类成 $w_i$ 组,每组通过单调队列遍历一遍即可获得最值, 而单调队列遍历一个元素的复杂度可以认为是 $O(1)$, 所以求 $f_{i,0},...,f_{i,W}$ 的复杂度就只有 $O(W)$.

关于单调队列的时间复杂度可以参考 单调队列.

在实现的时候，我们需要先枚举 $y$，这样才能保证枚举 $x$ 的时候利用单调队列进行优化，而单调队列中存储的是 $x-k$，并不存储 $k$，这样使用的时候需要通过 f[last][q.front() * w[i] + y] - q.front() * v[i] 获取对应的 $G_{x-k,y}$，不难发现 $x-k\in [x-k_i,x]$，因此在枚举 $x$ 的时候，我们需要删除队列中不在这个范围内的元素。

#include <array>
#include <deque>
#include <iostream>
 
constexpr int MAXV = 4e4 + 10;
constexpr int MAXN = 1e2 + 10;
 
using namespace std;
 
int n, W, last = 0, now = 1;
array<int, MAXN> v, w, k;
array<array<int, MAXV>, 2> f;
deque<int> q;
 
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> W;
  for (int i = 1; i <= n; i++) {
    cin >> v[i] >> w[i] >> k[i];
  }
  for (int i = 1; i <= n; i++) {
    for (int y = 0; y < w[i]; y++) {
      // 清空队列
      deque<int>().swap(q);
      for (int x = 0; x * w[i] + y <= W; x++) {
        // 弹出不在范围的元素
        while (!q.empty() && q.front() < x - k[i]) {
          q.pop_front();
        }
        // 保证队列单调
        while (!q.empty() && f[last][q.back() * w[i] + y] - q.back() * v[i] <
                                 f[last][x * w[i] + y] - x * v[i]) {
          q.pop_back();
        }
        q.push_back(x);
        f[now][x * w[i] + y] =
            f[last][q.front() * w[i] + y] - q.front() * v[i] + x * v[i];
      }
    }
    swap(last, now);
  }
  cout << f[last][W] << endl;
  return 0;
}

5 习题

例题 CF372C Watching Fireworks is Fun”

题目大意：城镇中有 $n$ 个位置，有 $m$ 个烟花要放。第 $i$ 个烟花放出的时间记为 $t_i$，放出的位置记为 $a_i$。如果烟花放出的时候，你处在位置 $x$，那么你将收获 $b_i-|a_i-x|$ 点快乐值。

初始你可在任意位置，你每个单位时间可以移动不大于 $d$ 个单位距离。现在你需要最大化你能获得的快乐值。

设 $f_{i,j}$ 表示在放第 $i$ 个烟花时，你的位置在 $j$ 所能获得的最大快乐值。

写出状态转移方程：$f_{i,j}=\max \{f_{i-1,k}+b_i-|a_i-j|\}$，其中 $j-(t_i-t_{i-1})\times d\le k\le j+(t_i-t_{i-1})\times d$。

尝试变形：

由于 $\max$ 里出现了一个确定的常量 $b_i$，我们可以将它提到外面去。

$f_{i,j}=\max \{f_{i-1,k}+b_i-|a_i-j|\}=\max \{f_{i-1,k}-|a_i-j|\}+b_i$

如果确定了 $i$ 和 $j$ 的值，那么 $|a_i-j|$ 的值也是确定的，也可以将这一部分提到外面去。

最后，式子变为：

$$f_{i,j}=\max \{f_{i-1,k}-|a_i-j|\}+b_i=\max \{f_{i-1,k}\}-|a_i-j|+b_i$$

接下来考虑单调队列优化。由于最终式子中的 $\max$ 只和上一状态中连续的一段的最大值有关，所以我们在计算一个新的 $i$ 的状态值时候只需将原来的 $f_{i-1}$ 构造成一个单调队列，并维护单调队列，使得其能在均摊 $O(1)$ 的时间复杂度内计算出 $\max \{f_{i-1,k}\}$ 的值，从而根据公式计算出 $f_{i,j}$ 的值。

总的时间复杂度为 $O(nm)$。

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
using ll = long long;
 
constexpr int MAXN = 150000 + 10;
constexpr int MAXM = 300 + 10;
 
ll f[2][MAXN];
ll a[MAXM], b[MAXM], t[MAXM];
int n, m, d;
 
int que[MAXN];
 
int fl = 1;
 
void init() {
  memset(f, 207, sizeof(f));
  memset(que, 0, sizeof(que));
  for (int i = 1; i <= n; i++) f[0][i] = 0;
  fl = 1;
}
 
void dp() {
  init();
  for (int i = 1; i <= m; i++) {
    int l = 1, r = 0, k = 1;
    for (int j = 1; j <= n;
         j++) {  // 在这里使用了单调队列的优化，推式子详见上面
      for (; k <= min(1ll * n, j + d * (t[i] - t[i - 1])); k++) {
        while (l <= r && f[fl ^ 1][que[r]] <= f[fl ^ 1][k]) r--;
        que[++r] = k;
      }
 
      while (l <= r && que[l] < max(1ll, j - d * (t[i] - t[i - 1]))) l++;
      f[fl][j] = f[fl ^ 1][que[l]] - abs(a[i] - j) + b[i];
    }
 
    fl ^= 1;
  }
}
 
int main() {
  cin >> n >> m >> d;
  for (int i = 1; i <= m; i++) cin >> a[i] >> b[i] >> t[i];
 
  // then dp
  dp();
  ll ans = -1e18;
  for (int i = 1; i <= n; i++) ans = max(ans, f[fl ^ 1][i]);
  cout << ans << endl;
  return 0;
}