AIOJ

Introduction

Prerequisite knowledge: Monotonic Queue, Monotonic Stack.

A monotonic queue is mainly used to maintain the range extrema of a pair of pointers that are monotonic nondecreasing, while a monotonic stack is mainly used to maintain the first number before/after the current value that is greater/less than it.

Note

To find a minimum, maintain a monotonically increasing/nondecreasing monotonic queue/stack, and vice versa.
When maintaining a monotonically increasing/decreasing comparison, use less than or equal to/greater than or equal to; when maintaining a monotonically nondecreasing/nonincreasing comparison, use less than/greater than.

Specific Steps for Monotonic Queue Optimization

Add the required elements: repeatedly add elements to the monotonic queue until the current element reaches the right boundary of the required interval, ensuring that all required elements are in the monotonic queue.
Remove the out-of-range front element: a monotonic queue essentially maintains the extrema of all inserted elements, but what we usually want is the extrema of an interval. Therefore, remove elements outside the left boundary to ensure that all elements in the monotonic queue are in the required interval.
Obtain the extrema: directly take the front of the queue as the answer.

Specific Steps for Monotonic Stack Optimization

Remove an invalid stack top: compare the current element with the stack top and remove stack-top elements that do not satisfy the monotonic stack property. Taking a monotonically increasing stack (that is, the stack top is the largest and the minimum is maintained) as an example, remove all stack elements greater than or equal to the current element.
Add the current element: simply push the current element onto the stack.

Monotonic Queue Optimization for Multiple Knapsack

Problem Description

You have $n$ items. Each item has weight $w_i$ , value $v_i$ , and quantity $k_i$ . You have a knapsack with weight capacity $W$ . You are now required to put items with the largest possible total value into the knapsack without exceeding the weight capacity. Find the maximum value.

If you are unfamiliar with knapsack DP, read Knapsack DP first. Let $f_{i,j}$ denote the maximum value obtained by putting the first $i$ items into a knapsack 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)

The time complexity is $O(W\sum k_i)$ .

Consider optimizing the transition of $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 written 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 can be written as:

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

This is transformed into a classic monotonic queue optimization form. $G_{x,y}$ can be calculated in $O(1)$ , so for a fixed $y$ , we can calculate in $O\left( \left\lfloor \dfrac{W}{w_i} \right\rfloor \right)$ time to obtain $g_{x,y}$ . Therefore, the complexity of calculating 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 complexity of this transition is reduced to $O(nW)$ .

In the implementation, we need to enumerate $y$ first, so that the monotonic queue can be used to optimize the enumeration of $x$ . The monotonic queue stores $x-k$ , not $k$ . When using it, obtain the corresponding $G_{x-k,y}$ through f[last][q.front() * w[i] + y] - q.front() * v[i]. It is not difficult to see that $x-k\in [x - k_i,x]$ , so when enumerating $x$ , we need to delete elements from the queue that are outside this range.

Reference Code

#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 outside the range
        while (!q.empty() && q.front() < x - k[i]) {
          q.pop_front();
        }
        // Ensure that 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 Problem CF372C Watching Fireworks is Fun

Problem statement: There are $n$ positions in a town, and $m$ fireworks are to be launched. The launch time of the $i$ -th firework is denoted by $t_i$ , and its launch position by $a_i$ . If you are at position $x$ when the firework is launched, you gain $b_i-|a_i-x|$ happiness points.

Initially, you may be at any position. In each unit of time, you can move a distance of no more than $d$ units. You now need to maximize the happiness you can obtain.

Let $f_{i,j}$ denote the maximum happiness obtainable when you are at position $j$ when the $i$ -th firework is launched.

Write the state transition equation: $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$ .

Try transforming it:

Since the $\max$ contains a definite constant $b_i$ , we can take it outside.

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

If the values of $i$ and $j$ are fixed, the value of $|a_i-j|$ is also fixed, so this part can also be taken outside.

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

Next, consider monotonic queue optimization. Since the $\max$ in the final expression depends only on the maximum value of a contiguous segment in the previous state, when calculating the state values for a new $i$ , we only need to construct a monotonic queue from the original $f_{i-1}$ and maintain the monotonic queue so that $\max\{f_{i-1,k}\}$ can be calculated in amortized $O(1)$ time, after which the value of $f_{i,j}$ can be calculated from the formula.

The total time complexity is $O(nm)$ .