Skip to content

Monotonic Queue/Stack Optimization

Introduction

Prerequisites: Monotonic Queue, Monotonic Stack.

Monotonic queues are mainly used to maintain the maximum/minimum value of an interval where both pointers move monotonically non-decreasing, while monotonic stacks are mainly used to maintain the first element before/after the current position that is greater/less than the current value.

Note
  • To find the minimum value, maintain a monotonically increasing/non-decreasing monotonic queue/stack, and vice versa.
  • When maintaining monotonic increasing/decreasing, use less than or equal to/greater than or equal to for comparisons; when maintaining monotonic non-decreasing/non-increasing, use less than/greater than.

Specific Steps for Monotonic Queue Optimization

  • Add required elements: Repeatedly add elements to the monotonic queue until the current element reaches the right boundary of the target interval, ensuring that all required elements are in the monotonic queue.
  • Pop out-of-bound front elements: The monotonic queue essentially maintains the extremum of all inserted elements, but we often want the extremum of an interval. Therefore, we pop elements outside the left boundary to ensure all elements in the monotonic queue are within the target interval.
  • Obtain the extremum: Directly take the front element as the answer.

Specific Steps for Monotonic Stack Optimization

  • Pop invalid top elements: By comparing the current element with the top of the stack, pop stack tops that do not satisfy the monotonic property. For example, for a monotonically increasing stack (i.e., the top is the largest, maintaining the minimum value), pop all stack elements that are greater than or equal to the current element.
  • Add the current element: Push the current element onto the stack.

Monotonic Queue Optimization for Multiple Knapsack

Problem Description

You have \(n\) items, each with weight \(w_i\), value \(v_i\), and quantity \(k_i\). You have a backpack with a weight capacity of \(W\). You need to select items to put into the backpack without exceeding the weight limit, maximizing the total value. Find the maximum value.

If you are unfamiliar with knapsack DP, please read Knapsack DP first. Let \(f_{i,j}\) denote the maximum value achievable by putting the first \(i\) items into a backpack with capacity \(j\). The naive transition equation is:

\[ f_{i,j}=\max_{k=0}^{k_i}(f_{i-1,j-k\times w_i}+v_i\times k) \]

Time complexity is \(O(W\sum k_i)\).

Consider optimizing the transition for \(f_i\). For convenience, let \(g_{x,y}=f_{i,x\times w_i+y},g'_{x,y}=f_{i-1,x\times w_i+y}\), where \(0\le y \lt w_i\). Then the transition equation can be expressed as:

\[ g_{x,y}=\max_{k=0}^{k_i}(g'_{x-k,y}+v_i\times k) \]

Let \(G_{x,y}=g'_{x,y}-v_i\times x\). Then the equation becomes:

\[ g_{x,y}=\max_{k=0}^{k_i}(G_{x-k,y})+v_i\times x \]

This transforms into a classic monotonic queue optimization form. \(G_{x,y}\) can be computed in \(O(1)\), so for a fixed \(y\), we can compute \(g_{x,y}\) in \(O\left( \left\lfloor \dfrac{W}{w_i} \right\rfloor \right)\) time. Therefore, the complexity to compute all \(g_{x,y}\) is \(O\left( \left\lfloor \dfrac{W}{w_i} \right\rfloor \right)\times O(w_i)=O(W)\). Thus, the total transition complexity reduces to \(O(nW)\).

In implementation, we need to first enumerate \(y\) to ensure that when enumerating \(x\), we can use monotonic queue optimization. The monotonic queue stores \(x-k\), not \(k\), so when using it, we need to obtain the corresponding \(G_{x-k,y}\) via f[last][q.front() * w[i] + y] - q.front() * v[i]. It is easy to see that \(x-k\in [x - k_i,x]\), so when enumerating \(x\), we need to remove elements in the queue that are not within this range.

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#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++) {
      // Clear the queue
      deque<int>().swap(q);
      for (int x = 0; x * w[i] + y <= W; x++) {
        // Remove elements that are out of range
        while (!q.empty() && q.front() < x - k[i]) {
          q.pop_front();
        }
        // Ensure the queue is monotonic
        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;
}

Exercises

Example CF372C Watching Fireworks is Fun

Problem Summary: There are \(n\) positions in a town, and \(m\) fireworks will be set off. The launch time of the \(i\)-th firework is \(t_i\), and its launch position is \(a_i\). If you are at position \(x\) when the firework is launched, you will gain \(b_i-|a_i-x|\) happiness points.

Initially, you can be at any position. You can move at most \(d\) units per unit time. Now you need to maximize the total happiness you can obtain.

Let \(f_{i,j}\) denote the maximum happiness you can obtain when the \(i\)-th firework is launched and you are at position \(j\).

The state transition equation is: \(f_{i,j}=\max\{f_{i-1,k}+b_i-|a_i-j|\}\), where \(j-(t_{i}-t_{i-1})\times d\le k\le j+(t_{i}-t_{i-1})\times d\).

Attempt to transform:

Since there is a constant \(b_i\) inside the \(\max\), we can factor it out.

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

If \(i\) and \(j\) are fixed, then \(|a_i-j|\) is also fixed and can be factored out.

Finally, the expression becomes:

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

Now consider monotonic queue optimization. Since the \(\max\) in the final expression only depends on the maximum value of a contiguous segment from the previous state, when computing a new state for \(i\), we only need to construct a monotonic queue from \(f_{i-1}\) and maintain it so that \(\max\{f_{i-1,k}\}\) can be computed in amortized \(O(1)\) time, thereby computing \(f_{i,j}\) according to the formula.

Total time complexity is \(O(nm)\).

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#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++) {  // Using monotonic queue optimization here, see above for derivation details
      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;
}
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用