单调队列优化 DP

引入

P1886 滑动窗口 /【模板】单调队列

定义一个队列 \(q\)，我们让 \(q\) 中的元素满足单调不降。因此当 \(x\) 入队时，从前往后让不在当前范围的元素出队，从后往前将 \(< x\) 的元素全部出队，然后加入 \(x\)。那么答案就是队列第一个元素。时间复杂度为 \(O(n)\)。

#include <bits/stdc++.h>

constexpr int N = 1e6 + 5;

int n, m, a[N];
int q[N], head, tail;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    std::cin >> a[i];
  }
  head = 0, tail = -1;
  for (int i = 1; i <= n; i++) {
    while (head <= tail && q[head] < i - m + 1) {
      head++;
    }
    while (head <= tail && a[q[tail]] > a[i]) {
      tail--;
    }
    q[++tail] = i;
    if (i >= m) {
      std::cout << a[q[head]] << ' ';
    }
  }
  std::cout << '\n';
  head = 0, tail = -1;
  for (int i = 1; i <= n; i++) {
    while (head <= tail && q[head] < i - m + 1) {
      head++;
    }
    while (head <= tail && a[q[tail]] < a[i]) {
      tail--;
    }
    q[++tail] = i;
    if (i >= m) {
      std::cout << a[q[head]] << ' ';
    }
  }
  std::cout << '\n';
  return 0;
}

例题

AcWing 298. 围栏

按照 \(S\) 进行排序，设 \(f(i, j)\) 表示当前为第 \(i\) 个工匠，粉刷了 \(j\) 块木板（可以存在未刷的木板），则：

• 不刷任何木板：\(f(i - 1, j)\)。
• 不刷当前木板：\(f(i, j - 1)\)。
• 刷连续一段木板，设粉刷 \([k + 1, j]\) 的木板：

时间复杂度为 \(O(n^2 m)\)。发现第三种情况我们需要 \(O(n)\) 转移，考虑优化。

将式子变形，可以得到：

可以用单调队列维护 \(f(i - 1, k) - k \times P_i\)。时间复杂度为 \(O(nm)\)。

#include <bits/stdc++.h>

constexpr int N = 105, M = 16005;

int n, m, f[N][M];
int q[M], head, tail;

struct Node {
  int L, P, S;
  bool operator<(const Node &rhs) {
    return S < rhs.S;
  }
} a[N];

int calc(int i, int j) {
  return f[i - 1][j] - a[i].P * j;
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int x, y, z;
    std::cin >> x >> y >> z;
    a[i] = {x, y, z};
  }
  std::sort(a + 1, a + 1 + m);
  for (int i = 1; i <= m; i++) {
    head = 0, tail = -1;
    q[++tail] = 0;
    for (int j = 1; j <= n; j++) {
      f[i][j] = std::max(f[i - 1][j], f[i][j - 1]);
      while (head <= tail && q[head] < j - a[i].L) {
        head++;
      }
      if (j < a[i].S) {
        while (head <= tail && calc(i, q[tail]) < calc(i, j)) {
          tail--;
        }
        q[++tail] = j;
        continue;
      }
      if (head <= tail) {
        f[i][j] = std::max(f[i][j], a[i].P * j + calc(i, q[head]));
      }
    }
  }
  std::cout << f[m][n] << '\n';
  return 0;
}