wiki - 算法小站

wiki 主题

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

算法基础搜索数据结构字符串数学图论动态规划计算几何杂项

动态规划

背包模型

dp优化

凸壳优化

单调队列优化

[[ item.c ]]

单调队列优化

## 单调队列优化
单调队列优化，可以处理一部分 dp 式子
```math
\displaystyle
dp(i) = \max_{1 \leqslant j < i} (dp(j) + w(j, i))
```
直接做是$$O(n^2)$$的，希望通过决策单调性或者$$w(i, j)$$的性质，让它优化到$$O(n), O(n \log n)$$

单调队列优化，一般是针对$$w(i, j)$$，直接求最大值，而四边形不等式或者是斜率优化
则是根据决策单调性来求最大值

## 单调队列思想
一般是有一个限制，即求**一段区间**的最值，这里以**最大值**举例，假设有一个窗口$$l, r$$
两个端点的**限制**，（假设说用$$f(i)$$表示）都是单调递增的
```math
\displaystyle
f(l_1) \leqslant f(l_2) \leqslant \cdots \leqslant f(l_n) \\
f(r_1) \leqslant f(r_2) \leqslant \cdots \leqslant f(r_n)
```
1）每一次考虑一个新的位置$$i$$，看一下左端点是否**出界**，如果$$|g(i) - g(que.front)| > x$$
出界，那么弹出队列左端点（这是标准的队列操作）

2）右端点移动，假设说新进来了一个数$$a_i$$，如果$$dp(i) \geqslant dp(que.back())$$
那么`que.back()`这个数永远不会成为最大值，就把这样的数删掉
这样队列中的数就是单调递减的了

3）要求最大值，直接取`dp[ que.front() ]`即可

### 多重背包
**[多重背包3](http://oj.daimayuan.top/course/8/problem/168)**
有`n`种物品放到一个袋子，袋子的容量是`m`，第`i`种物品的体积是$$v_i$$
放进袋子有$$w_i$$的收益，第$$i$$种物品有$$l_i$$个，求最大收益

**算法分析**
```math
\displaystyle
dp(i, V) = \max_{k = 0}^{C_i} dp(i-1, V - k \cdot v_i) + k \cdot w_i \\
\quad \\
ndp(x) = \max_{j = 0}^{C_i} dp(x - j \cdot v_i) + k \cdot w_i
```
观察这个式子，$$x$$从$$\\{x, x - v, x - 2v, \cdots,  x - cv\\}$$转移过来的
不难想到，可以根据$$\bmod v$$来**分类**

> 枚举$$i$$，令$$v = v_i, w = w_i, c = c_i$$，同时按照余数分类
枚举余数$$r \in [0, v)$$

那么我们有背包的实际体积$$x$$，拥有的最大价值为$$ndp(x)$$
其中$$x = kv + r$$，其中$$k \leqslant \lfloor \dfrac{m-r}{v} \rfloor = kmax$$

> 枚举$$k \in [0, kmax]$$

有转移方程
```math
\displaystyle
ndp(kv + r) \leftarrow \max_{j = 0}^{c} dp((k-j)v + r) + j\cdot w_i
```
本来应该枚举$$j$$的，**但可以挖掘单调性**
首先$$ndp(kv + r)$$，$$v, r$$是我们枚举的，可以认为是**确定的**

因此$$kv + r$$的单调性，**只取决**于$$k$$的单调性，方程可以简写为
```math
\displaystyle
f_2(k) \leftarrow \max_{j = 0}^{c} f_1(k - j) + j \cdot w
```
令$$p = k - j, p \in [k-c, k]$$，那么
```math
\displaystyle
f_2(k) \leftarrow \max_{p = k - c}^{k} (f_1(p) - p\cdot w) + kw
```
注意到$$k = [0, kmax]$$是我们要枚举的，而$$p \in [k-c, k]$$区间两个端点
都关于$$k$$**单调递增**
那么用单调队列去维护$$\\{f_1(p) - p \cdot w \\}$$，让队列单调减
最大值取队头元素即可

> 细节，这里的$$f(k), f(p)$$对应的$$k, p$$并不是我们要的`dp 值`
这些值只是我们用来分析的，要记得还原成$$dp$$值

枚举了$$k$$，那么对应的**实际的**$$x = kv + r$$
维护单调队列，用一个二元组$$(p, \\{dp(pv+r) - pw \\}) = (p, val)$$来表示
其中`val`用来检查单调性，`p`用来检查队头是否出界

单调队列扩展的时候，必须保证$$(p, val)$$，`val`**是严格单调减的**

```bash
void solve(int cas) {
    int n, m;
    cin >> n >> m;

using arr = array<int, 3>;
    vector<arr> a(n+1);

for (int i = 1; i <= n; i++) {
        auto &[vi, wi, ci] = a[i];
        cin >> vi >> wi >> ci;
    }

vector<i64> dp(m+5, 0);
    for (int i = 1; i <= n; i++) {
        const auto &[v, w, c] = a[i];
        auto ndp = dp;

for (int r = 0; r < v; r++) {
            int kmax = (m - r) / v;
            if (kmax < 0) continue;

using pint = pair<int, i64>;
            // (p,  dp[pv+r]-pw)
            deque<pint> que;

for (int k = 0; k <= kmax; k++) {
                i64 x = k * v + r;
                i64 val = dp[k*v+r] - 1LL*k*w;

while (que.size() and que.back().second <= val) que.pop_back();
                que.push_back(make_pair(k, val));
                while (que.size() and que.front().first < k - c) que.pop_front();

if (que.size()) {
                    auto [p, val] = que.front();
                    i64 dpv = val + 1LL * k * w;
                    ndp[x] = max(ndp[x], dpv);
                }
            }
        }
        dp.swap(ndp);
    }

auto ans = *max_element(dp.begin(), dp.end());
    cout << ans << "\n";
}
```

## Codeforces Round 219 (Div. 1)
### D
**[C. Watching Fireworks is Fun](https://codeforces.com/contest/372/problem/C)**
主街上有$$n$$个点，编号$$1 \to n$$，每个相邻点之间的距离是`1`
发射`m`组烟花，第`i`组将在时间$$t_i$$，并且在点$$a_i$$处发射
如果此时你位于点$$x$$，你会获得幸福值$$b_i - |a_i - x|$$
可以在一个时间单位内，最多移动`d`个长度单位，同时你可以在初始时刻
选择位于任意一个点，需要最大化可以获得的幸福值

可能会在同一时间发射多组烟花，$$n \leqslant 10^5, m \leqslant 300$$

**算法分析**
对烟花绽放的时间，按从小到大排序，$$dp(i, x)$$表示第`i`个烟花绽放的时候在`x`位置能够获取的最大幸福值
那么从$$i-1 \sim i$$，能够移动的距离是$$D = (t\_i - t\_{i-1})d$$

枚举第$$i-1$$个烟花绽放时候，所在的位置$$y$$
因为$$i$$时刻可能有多个烟花绽放，所以可以预处理每一个烟花$$(t_i, a, b)$$对幸福值的贡献
即$$cost = \sum (b - |a - x|)$$
```math
\displaystyle
dp(i, x) = \max_{x-D \leqslant y \leqslant x+D} dp(i-1, y) + cost
```
这是一个很标准的单调队列优化`dp`的转移

```bash
void solve(int cas) {
	// 省略无关的输入输出
    // fire (ti, ai, bi)
    vector<i64> dp(n+5, 0);

for (int i = 1; i <= N; i++) {
        auto ndp = dp;
        ndp.assign(n+5, -inf<i64>);

i64 D = (i == 1 ? inf<i64> : 1LL * (fire[i][0][0] - fire[i-1][0][0]) * d);

using pint = pair<int, i64>;
        deque<pint> que;

// (p, val)
        int r = 1;
        for (int x = 1; x <= n; x++) {
            i64 cost = 0;
            for (auto [ti, ai, bi] : fire[i]) {
                cost += 1LL * bi - 1LL * llabs(ai - x);
            }

int rmax = min(1LL * n, x + D);
            while (r <= rmax) {
                while (que.size() and que.back().second <= dp[r]) que.pop_back();
                que.emplace_back(r, dp[r]);
                r++;
            }

while (que.size() and que.front().first < x - D) que.pop_front();

if (que.size()) {
                auto [y, dpv] = que.front();
                chmax(ndp[x], dpv + cost);
            }
        }

dp.swap(ndp);
    }

auto ans = *max_element(dp.begin(), dp.end());
    cout << ans << "\n";
}
```

## 瑰丽华尔兹
**[瑰丽华尔兹](https://ac.nowcoder.com/acm/problem/17395)**
舞厅是一个$$n \times m$$的矩阵，有一些障碍，也有空地，钢琴在每个时刻都会朝着相邻方向滑动`1`格
滑动的方向是给定的，钢琴的初始位置也给出
现在每个时刻两种决策，施魔法或者不施魔法
施魔法的话，钢琴会原地不动，否则会移动，问钢琴能够移动的最长距离
注意，钢琴不能碰到障碍或者出界，否则游戏结束

**算法分析**
以**时间段**进行动态规划，假设现在考虑第$$i$$个时间段，枚举这个时间段结束后在的位置$$(x, y)$$
所经过的最长路径不妨记为$$ndp(x, y)$$，令$$T = t_i - s_i$$
```math
\displaystyle
ndp = dp \\
ndp(x, y) \leftarrow \max_{x_0, y_0} dp(x_0, y_0) + dist((x_0, y_0), (x, y)) 
```
其中要满足限制
1) $$(x_0, y_0) \to (x, y)$$在$$d_i$$方向上无障碍
2) $$dist((x_0, y_0), (x, y)) \leqslant T$$

这里不妨只考虑**向右的方向**，那么假设说上一个时段在$$k$$
```math
\displaystyle
ndp(x, y) \leftarrow \max_{y - k \leqslant T} dp(x, k) + (y - k) \\
ndp(x, y) \leftarrow \max_{k \geqslant y - T} (dp(x, k) - k) + y
```
这是一个很典型的可以用单调队列优化求解的表达式

> 现在问题是有`4`个方向，怎么办？我们可以用**坐标变换**
尝试把`4`个方向的坐标移动，**统一成**向右移动的情况

假设现在考虑坐标$$(x, y)$$，标准的移动方向是$$(x, y) \to (x, y+1)$$

1) 向左移动，$$(x, y) \to (x, y - 1)$$，现在需要考虑坐标变换$$f(y)$$
使得有映射$$(x, y) = (x, f(y))$$，那么坐标变换对应成$$(x, f(y-1)) \to (x, f(y) + 1)$$
也就是说，我们要使得$$f(y-1) = f(y) + 1$$，最简单的，令$$y = m - y + 1$$
从而$$(x, y)$$对应$$(x, m - y + 1)$$

2) 向右移动，标准方向，坐标不变

3) 向下移动，目标是$$(x, y) \to (x+1, y)$$，此时交换$$(x, y) = (y, x)$$
之后**对新坐标按向右移动的标准方向来处理**，$$(y, x) \to (y, x+1)$$就完成了
需要做的变换是$$(x, y) \to (y, x)$$

4）向上移动，目标是$$(x, y) \to (x-1, y)$$，此时交换$$(x, y) = (y, x)$$
再令$$(y, x) = (y, n - x + 1)$$，这样按向右移动来处理$$(y, n - x + 2)$$
（之后变回来就是$$\to (y, x-1) \to (x-1, y)$$）
需要做的变换是$$(y, n - x + 1)$$

同样的方式构造逆变换，值得注意的是，向上移动存在`2`步，$$(A_1A_2)^{-1} = A_2^{-1}A_1^{-1}$$
逆变换是$$(x, y) \to (n-y+1, x)$$

> 这样算法实现就简单了

1）枚举$$(x, y)$$，先做一次坐标变换，$$dp \to dp2$$，同时原来的图形`G`也要对应变换

2）对于每个$$y$$，分段，考虑$$y \in [yl, yr]$$，其中$$[yl, yr]$$是**极长的，没有障碍物的一段**（双指针可以轻松实现）
对于每个这样的$$y$$，执行上面的**单调队列优化 dp**，新的 dp 值用`ndp2`维护

3）做完$$y = m$$的时候，再做一次坐标变换，$$ndp2 \to ndp$$
然后`dp.swap(ndp)`即可

### 算法实现
```bash
void solve(int cas) {
    int n, m, X, Y, K;
    cin >> n >> m >> X >> Y >> K;

vector<string> g(n+1);
    for (int i = 1; i <= n; i++) {
        cin >> g[i];
        g[i] = " " + g[i];
    }

using arr = array<int, 3>;
    vector<arr> a(K);
    for (int i = 0; i < K; i++) {
        auto &[si, ti, di] = a[i];
        cin >> si >> ti >> di;
    }

using pint = pair<int, int>;
    auto mapping = [&](int x, int y, int d) -> pint {
        if (d == 1) return pint{y, n - x + 1};
        if (d == 2) return pint{y, x};
        if (d == 3) return pint{x, m - y + 1};
        if (d == 4) return pint{x, y};

return {-1, -1};
    };

auto trans = [&](int d, const vector<vector<i64> > &dp, vector<vector<i64> > &dp2, vector<string> &g2) -> void {
        for (int x = 1; x <= n; x++) {
            for (int y = 1; y <= m; y++) {
                auto [nx, ny] = mapping(x, y, d);

dp2[nx][ny] = dp[x][y];
                g2[nx][ny] = g[x][y];
            }
        }
    };
    auto getback = [&](int d, vector<vector<i64> > &ndp, const vector<vector<i64> > &ndp2) -> void {
        for (int x = 1; x <= n; x++) {
            for (int y = 1; y <= m; y++) {
                auto [nx, ny] = mapping(x, y, d);

ndp[x][y] = ndp2[nx][ny];
            }
        }
    };

vector dp(n+5, vector<i64>(m+5, -inf<i64>));
    dp[X][Y] = 0;

for (int i = 0; i < K; i++) {
        auto [si, ti, di] = a[i];
        auto T = ti - si + 1;

int N = (di == 1 or di == 2) ? m : n;
        int M = (di == 1 or di == 2) ? n : m;

vector dp2(N+5, vector<i64>(M+5, -inf<i64>));
        vector<string> g2(N+1, string(M+1, ' '));

trans(di, dp, dp2, g2);
        auto ndp2 = dp2;

for (int x = 1; x <= N; x++) {
            for (int j = 1; j <= M; j++) {
                auto p = j;
                while (p <= M and g2[x][p] == 'x') p++;

auto yl = p;
                p = yl;
                while (p + 1 <= M and g2[x][p+1] == '.') p += 1;
                auto yr = p;

// [yl...yr] dp
                deque<pair<int, i64> > que;
                // (y, val = dp[x][y] - y)
                for (int y = yl; y <= min(M, yr); y++) {

while (que.size() and dp2[x][y] - y >= que.back().second) que.pop_back();
                    que.emplace_back(y, dp2[x][y] - y);
                    
                    while (que.size() and abs(y - que.front().first) > T) que.pop_front();

if (que.size()) {
                        auto dpv = que.front().second + y;
                        chmax(ndp2[x][y], dpv);
                    }

}
                
                j = yr;
            }
        }

vector ndp(n+5, vector<i64>(m+5, -inf<i64>));
        getback(di, ndp, ndp2);
        
        dp.swap(ndp);
    }

i64 ans = 0;
    for (int x = 1; x <= n; x++) {
        for (int y = 1; y <= m; y++) chmax(ans, dp[x][y]);
    }

cout << ans << "\n";
}
```

## Codeforces Round 922 (Div. 2)
### D
**[D. Blocking Elements](https://codeforces.com/problemset/problem/1918/D)**
给定一个序列，需要阻断一些元素，假设阻断下标是$$(b_1, b_2, \cdots, b_m)$$的元素
数组的代价定义为以下二者的最大值

被阻断元素的和$$a\_{b\_1} + a\_{b\_2} + \cdots + a\_{b\_m}$$
移除被阻断元素后，形成若干连续子段，求这些子段和的最大值
`[1, 4, 5, 3, 3, 2]`移除`a[2], a[5]`，代价是`4 + 3 = 7`
连续子段是`[1], [5, 3], [2]`，子段代价是`8`，因此最大值是`8`
现在要最小化这个最大值

**算法分析**
二分一个$$x$$
考虑第一种限制，只要找到若干个数，使得它们和的最小值$$\leqslant x$$，即合法
同时还必须满足第二种限制

假设说对于$$i$$
```math
\displaystyle
dp(i) = \min_{S_{i-1} - S_{j} \leqslant x} dp(j) + a_i
```
其中`a[j+1], a[j+2], ...., a[i-1]`是我们要考虑的另外一种限制，它们的和必须$$\leqslant x$$

注意到$$S_i$$是关于$$i$$单调递增的，上式就是一个很标准的单调队列优化

> 这个问题和之前的不一样的地方是什么？

实际上是在约束$$S\_{i-1} - S_j \leqslant x$$上面
我们考虑位置$$i \in [1, n+1]$$，此时$$[0\cdots i-1]$$这些位置的相关`dp 值`
已经用单调队列维护起来了

需要先执行`while (que.size() and S[i-1] - S[ que.front().first ] > x), then que.pop_front()`
保证队列左端点的限制
然后**立马更新**`dpv = que.front().second,   dp[i] = max(dp[i], dpv + a[i])`

之后再根据队尾元素的单调性，将新算出来的`(i, dp[i])`加入队尾

```bash
for (int i = 1; i <= n + 1; i++) {
	while (que.size() and s[i-1] - s[que.front().first] > x) que.pop_front();
	if (que.size()) {
		auto [j, dpv] = que.front();
		chmin(dp[i], dpv + a[i]);
	}
	while (que.size() and dp[i] <= que.back().second ) que.pop_back();
	que.emplace_back(i, dp[i]);
}
return dp[n+1] <= x;
```

> 细节，但可能会致命的错误

```math
\displaystyle
dp(i) = \min_{S_{i-1} - S_{j} \leqslant x} dp(j) + a_i
```
这个和以往的$$ndp(i) = \max dp(j) + cost$$表达式不同
以往的表达式，`for 当前阶段的 i 的时候`，旧的`dp[i]`已经算出来了
可以根据`dp`的单调性，来将`dp[i]`进单调队列维护

而现在的表达式，$$dp(i) = \max dp(j) + a_i$$
我们`for 当前位置 i`的时候，$$dp(i)$$还没有算出来，是不能放入单调队列中的

先用队列计算出并更新`dp[i]`，再把更新后的 `dp[i]` 按单调性 push 进队列供后续使用
（如果像之前那样一开始就 push，得到的是旧的 dp[i]，通常是 inf，导致错误）

另外，$$i$$的终止节点，因为有$$S\_{i-1}$$的限制，需要设置一个哨兵`a[n+1]`
`dp`的终止节点应该是`dp[n+1] <= x`，而不是`dp[n]`

看完文章有啥想法

算法小站

wiki 主题

动态规划

单调队列优化

目录