动态规划 单调队列优化

引用: 单调栈和单调队列是一种常用的优化思想，可以通过维护一个有序的数据结构，排除不可能的决策，提高算法的效率。其中，单调栈适用于解决求解左边第一个比自己大（小）的点等问题，而单调队列适用于维护左区间最值等问题。通过这两种思想，可以优化动态规划等算法的时间复杂度。

引用: 在求解最大子序和问题时，可以使用单调队列优化。假设当前位置为i，我们可以维护一个单调递减的队列，其中存放的是前i个位置的子序和。每次加入新的元素时，可以通过比较队列中的元素和当前元素的大小，若当前元素更大，则弹出队列中的元素，直到队列为空或者队尾元素大于当前元素。然后将当前元素加入队列。最终，队列中的最大值即为最大子序和。

引用: 单调队列优化动态规划是通过将可转移状态存入一个单调队列中，来进行状态转移的一种方法。这个可转移状态要满足连续且单调的特性。具体原理是，如果一个选手比你小，但是比你强，那么你就可以退役了。在动态规划中，可以先使用朴素的dp方法找到一种方法，再根据单调队列优化。

例题1：求左边第1个比自己大的点
问题分析：将可转移给第i个点的对象存入栈中。假设i可以从j,k转移而来，其中j < k。栈中的元素是一个单调递减的栈。每次加入第i个点，都会依次将比ai小的弹出，最后栈顶元素即为答案。

例题2：维护左区间最值
问题分析：通过维护一个单调递减的队列，存储左区间的最值。在每次更新元素时，比较队列中的元素和当前元素的大小，若当前元素更大，则弹出队列中的元素，直到队列为空或者队尾元素大于当前元素。然后将当前元素加入队列。

相关问题

单调队列优化动态规划

单调队列优化是一种常用的优化技巧，用于加速动态规划的求解过程。它主要应用于一类具有状态转移函数具有单调性的动态规划问题。

在使用动态规划求解问题时，通常会遇到一个状态转移函数，该函数具有单调性。也就是说，如果状态i的最优解比状态j的最优解好，且i在j之前，那么在求解状态j时，状态i不会对结果产生影响。

单调队列优化的核心思想是维护一个递增或递减的队列，用于记录可能成为最优解的状态。在状态转移过程中，我们只需要考虑队列中满足单调性要求的状态。

具体步骤如下：
1. 定义一个队列，用于存储可能成为最优解的状态的索引。
2. 初始化队列为空。
3. 从左到右遍历状态，并依次进行如下操作：
- 如果队列不为空且队首元素已经不在有效范围内（根据题目要求定义），则将队首元素出队。
- 如果队列不为空，则当前状态与队尾元素进行比较，如果当前状态的最优解不如队尾元素的最优解好，则将队尾元素出队，直到队列为空或者当前状态的最优解比队尾元素的最优解好为止。
- 将当前状态的索引入队。
4. 根据题目要求，计算每个状态的最优解。

通过单调队列优化，可以减少状态的遍历次数，从而提高动态规划的效率。但需要注意的是，单调队列优化并不适用于所有的动态规划问题，只适用于具有单调性的状态转移函数。在使用时需要仔细分析问题的性质和要求。

单调队列优化多重背包代码

下面是单调队列优化多重背包的代码实现：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 10010;
int f[N];
int q[N], v[N], w[N];
int n, m;

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= v[i]; j -- )
        {
            int hh = 0, tt = -1;
            for (int k = 0; k * v[i] <= j; k ++ )
            {
                int t = f[j - k * v[i]] - k * w[i];
                while (hh <= tt && q[tt] < t) tt -- ;
                q[ ++ tt] = t;
                if (hh <= tt) f[j] = max(f[j], q[hh] + k * w[i]);
            }
        }
    cout << f[m] << endl;
    return 0;
}

该代码中的单调队列使用了双端队列来实现，队头表示队列中最大的元素，队尾表示队列中最小的元素。当加入一个新的元素时，将队列中所有小于该元素的元素弹出，然后将该元素压入队尾。同时，如果队头元素已经超出了当前的背包容量，需要将队头元素弹出。

在遍历所有物品和背包容量的组合时，每次需要清空队列。对于每个物品，从当前背包容量到该物品体积之间的所有容量，都需要计算出最大的价值。在计算价值时，需要使用单调队列进行优化。

该算法的时间复杂度为 O(N*V)，空间复杂度为 O(V)，其中 N 表示物品的数量，V 表示背包的容量。