跳转至

單調隊列/單調棧優化

介紹

前置知識：單調隊列、單調棧。

例題 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|\}\)

這裏的 \(k\) 是有範圍的，\(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)\)。

參考代碼 
 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;
typedef long long ll;

const int maxn = 150000 + 10;
const 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;
}

講完了，讓我們歸納一下單調隊列優化動態規劃問題的基本形態：當前狀態的所有值可以從上一個狀態的某個連續的段的值得到，要對這個連續的段進行 RMQ 操作，相鄰狀態的段的左右區間滿足非降的關係。

單調隊列優化多重揹包

問題描述

你有 \(n\) 個物品，每個物品重量為 \(w_i\)，價值為 \(v_i\)，數量為 \(k_i\)。你有一個承重上限為 \(W\) 的揹包，現在要求你在不超過重量上限的情況下選取價值和儘可能大的物品放入揹包。求最大價值。

不瞭解揹包 DP 的請先閲讀 揹包 DP。設 \(f_{i,j}\) 表示前 \(i\) 個物品裝入承重為 \(j\) 的揹包的最大價值，樸素的轉移方程為

\[ f_{i,j}=\max_{k=0}^{k_i}(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}=f_{i-1,x\times w_i+y}\)，則轉移方程可以表示為：

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

設 \(G_{x,y}=g'_{x,y}-v_i\times x\)。則方程可以表示為：

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

這樣就轉化為一個經典的單調隊列優化形式了。\(G_{x,y}\) 可以 \(O(1)\) 計算，因此對於固定的 \(y\)，我們可以在 \(O\left( \left\lfloor \dfrac{W}{w_i} \right\rfloor \right)\) 的時間內計算出 \(g_{x,y}\)。因此求出所有 \(g_{x,y}\) 的複雜度為 \(O\left( \left\lfloor \dfrac{W}{w_i} \right\rfloor \right)\times O(w_i)=O(W)\)。這樣轉移的總複雜度就降為 \(O(nW)\)。

習題

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Marcythm, hsfzLZH1, Ir1d, greyqz, Anguei, billchenchina, Chrogeek, ChungZH
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用