单调队列优化 DPCSP-S

💡 核心思想

单调队列优化 DP 用于解决"滑动窗口最值型"DP 问题。典型场景：dp[i] = max{ dp[j] + val(i,j) }，其中 j 的范围是一个滑动窗口 [i-k, i-1]。直接用单调队列维护窗口内的 dp 值，将 O(n·k) 优化到 O(n)。经典应用：多重背包优化、单调子序列、任务调度。

🎯 直觉理解

想象你在排队买票，窗口只能看到前面 k 个人。你想找前面 k 个人里谁最划算（dp 值最大）。单调队列就像一个"智能排队机"：新人来了，如果比前面所有人都强，前面的人永远没机会了，直接踢走；如果窗口滑走了，就把队头的人请出去。

📝 算法流程

1. 写出原始 DP 方程，确定 j 的取值范围
2. 将 j 按某个模数分组（通常是物品重量）
3. 每组内用单调队列维护 dp 值
4. 队列中存下标，保持 dp 值单调递减（求最大）或递增（求最小）
5. 队头超出窗口范围时出队
6. 当前 dp 值入队前，从队尾弹出所有更差（更不可能成为最优）的值

$$dp[i] = \max_{j \in [i-k, i-1]} \{ dp[j] + w(i, j) \}$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;

// 单调队列优化多重背包模板
// dp[i] = max(dp[i], dp[i - j*w] + j*v) for j in [0, cnt]
const int N = 200005;
int dp[N];

void monoQueueKnapsack(int W, int w, int v, int cnt) {
    // 按模 w 分组
    for (int r = 0; r < w; r++) {
        deque> dq; // (下标, dp值)
        for (int k = 0; r + k * w <= W; k++) {
            int i = r + k * w;
            int val = dp[i] - k * v;
            
            // 队头超出窗口
            while (!dq.empty() && dq.front().first < k - cnt) dq.pop_front();
            
            // 队尾维护单调性（求最大）
            while (!dq.empty() && dq.back().second <= val) dq.pop_back();
            
            dq.push_back({k, val});
            dp[i] = dq.front().second + k * v;
        }
    }
}

int main() {
    int n = 3, W = 10;
    // 物品：(w, v, cnt)
    memset(dp, -0x3f, sizeof(dp));
    dp[0] = 0;
    monoQueueKnapsack(W, 3, 4, 2); // 重量3，价值4，最多2个
    cout << dp[W] << endl;
    return 0;
}

⚠️ 常见坑点

📚 相关题目