📖 第 6.6 章 ⏱️ 约 60 分钟 💎 Platinum

第 6.6 章：DP 优化

6.6.0 从三道超时的题出发

前面几章你已经学会设计状态和转移。但竞赛里更残酷的问题是：状态设计对了、转移也想对了，复杂度却过不了。看三道题：

题 1（多重背包）： N ≤ 100 件物品，物品 i 重 w_i、价值 v_i、最多选 k_i 件（k_i ≤ 100），背包容量 W ≤ 40000。按 6.2 章的做法枚举「选几件」，转移一层是 O(W × k_i)，总复杂度 O(N·W·k) 达 4×10⁸，超时。

题 2（玩具装箱，HNOI2008）： N ≤ 5×10⁴ 个玩具排成一排，分成若干段，段 [l,r] 的代价是 (r-l+1+Σc-L)²，求最小总代价。朴素 DP f[i] = min{f[j] + 代价} 是 O(N²) = 2.5×10⁹，超时。

题 3（石子合并，大数据版）： N ≤ 5000 堆石子合并成一堆。区间 DP 枚举分割点是 O(N³) ≈ 1.25×10¹¹，超时。

三道题状态都对、转移都对，唯一的问题是转移里有冗余：

题 1：计算 dp[i][j] 时枚举了 k，但 dp[i][j-2w]、dp[i][j-w]……这些「邻居」的转移里已经算过几乎同一批候选值——重复的滑动窗口最值问题；
题 2：每个 f[i] 都从头枚举所有 j，但相邻 i 的最优决策点在大多数情况下靠得很近——决策点的位置有规律；
题 3：dp[l][r] 枚举了所有分割点 k，但最优分割点满足 opt[l][r-1] ≤ opt[l][r] ≤ opt[l+1][r]——决策单调，不需要全枚举。

本章讲三种利用这些冗余的经典优化：

小节	优化技术	利用什么冗余	复杂度变化	代表题
6.6.1	单调队列优化	转移是「滑动窗口最值」	O(N·W·k) → O(N·W)	多重背包
6.6.2	斜率优化	转移是「一次函数截距最值」	O(N²) → O(N)	玩具装箱
6.6.3	决策单调性	最优决策点随下标单调移动	O(N³) → O(N²)（区间 DP）	石子合并

6.6.1 单调队列优化

使用场景： 转移可以整理成 dp[i] = max{ dp[j] + cost(j,i) }，且当 i 固定时，候选的 j 构成一个长度固定的滑动窗口，窗口内的「有效部分」只与 j 有关。

核心思路： 把「窗口内每个 j 都试一遍」变成「单调队列维护窗口最值」，每个元素入队出队各一次，均摊 O(1)。

例题：多重背包

回顾 6.2 章的多重背包转移（dp[i][j] = 前 i 件物品、容量 j 的最大价值）：

dp[i][j] = max{ dp[i-1][j - k*w[i]] + k*v[i] : 0 ≤ k ≤ min(k[i], j/w[i]) }

枚举 j 和 k，一层是 O(W·k)。下面看冗余在哪。

第一步：按余数分组。 固定物品 i，容量 j 能到达的所有状态是 j = x·w + y（y = j mod w，x = j div w）。对同一个余数 y，把状态排成一列：

g[x] = dp[i-1][x*w + y]        （上一层的值，按 x 排列）

以 w=3 为例，余 y=1 的一列是 j = 1, 4, 7, 10, 13, ...，对应 x = 0, 1, 2, 3, 4, ...。

第二步：写出列内的转移。 在这一列里，dp[i][x·w+y] 由下面的最大值决定（令 k = x - x'，即选的件数）：

g'[x] = max{ g[x-k] + k*v : 0 ≤ k ≤ min(K, x) }

其中 K = k[i]。这一步还没省事——但注意 k·v = (x - (x-k))·v，拆开：

g'[x] = max{ g[x-k] - (x-k)·v : 0 ≤ k ≤ min(K, x) } + x·v

令 G[x] = g[x] - x·v，则：

g'[x] = max{ G[x-k] : 0 ≤ k ≤ min(K, x) } + x·v
       = max{ G[t] : x-K ≤ t ≤ x } + x·v        （t = x-k）

这就是一个长度为 K+1 的滑动窗口最大值！ 用单调队列，均摊 O(1) 求出每个 g'[x]。

复杂度： 枚举 y 是 w 种，每个 y 内枚举 x 是 W/w 步——合计正好 O(W)，总复杂度降为 O(N·W)。

完整代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; long long W;
    cin >> n >> W;
    vector<long long> w(n), v(n);
    vector<int> k(n);
    for (int i = 0; i < n; i++) cin >> w[i] >> v[i] >> k[i];

    vector<long long> f(W + 1, 0);   // f[j] 当前为「处理完前 i 件物品」
    vector<long long> g(W + 1);      // 上一层（前 i-1 件）的值
    vector<long long> nf(W + 1);     // 新一层
    deque<int> dq;                   // 存 x（该同余类中物品的「件数」层号）

    for (int i = 0; i < n; i++) {
        g = f;                       // g = f[i-1][*]
        for (int y = 0; y < w[i] && y <= W; y++) {
            dq.clear();
            long long wi = w[i], vi = v[i];
            int K = k[i];
            // x = 0,1,2,...，对应容量 j = x*w+y
            int maxX = (int)((W - y) / wi);
            for (int x = 0; x <= maxX; x++) {
                long long j = x * wi + y;
                // 窗口是 [x-K, x]：弹出队首越界的 x
                while (!dq.empty() && dq.front() < x - K) dq.pop_front();
                // 队尾单调：弹掉所有 G 值不优于新 x 的旧队尾
                while (!dq.empty() &&
                       g[dq.back() * wi + y] - dq.back() * vi
                           <= g[j] - (long long)x * vi)
                    dq.pop_back();
                dq.push_back(x);
                // 队首是窗口内 G 最大的 x'
                nf[j] = g[dq.front() * wi + y] - dq.front() * vi + (long long)x * vi;
            }
        }
        f.swap(nf);
    }
    cout << f[W] << "\n";
    return 0;
}

样例：

输入：
2 10
2 3 3
3 5 2

输出：
16

手算核对：物品 1（重 2、价值 3、限 3 件）+ 物品 2（重 3、价值 5、限 2 件）。最优方案是 3 件物品 1（重 6、价值 9）+ 2 件物品 2（重 6、价值 10），总重 12 > 10 ✗。改取 2 件物品 1 + 2 件物品 2：重 4+6=10 ≤ 10，价值 6+10=16。✓

何时使用： 转移中出现 max/min{ dp[j] + 只与 j 有关的东西 } 且 j 的范围是一个平移的固定窗口（多重背包、跳跃距离限制类题）。若窗口两端都随 i 移动且不固定长度，仍可用单调队列，只需按实际窗口弹两端。

6.6.2 斜率优化

使用场景： 转移中出现了乘积项（如 (s[i]-s[j])² 展开后有 s[i]·s[j]），单调队列救不了，但把每个决策 j 看成平面上的点、把转移看成直线的截距后，最优决策落在凸壳上。

第一步：化简——消掉式子里的 i 和 j

令 s[i] = pre[i] + i（把 i 折进前缀和），L' = L + 1，则：

$$f_i = \min_{j<i}{, f_j + (s_i - s_j - L')^2 ,}$$

第二步：拆平方，按「与谁有关」分组

展开 (s_i - s_j - L')² 并把只与 i 有关的项移到左边：

$$f_i - (s_i - L')^2 = \min_{j<i}{, \underbrace{(f_j + s_j^2)}{只与\ j\ 有关} + \underbrace{2(L'-s_i)}{斜率}\cdot \underbrace{s_j}_{只与\ j\ 有关} ,}$$

回忆一次函数的斜截式 y = kx + b，即 b = y - kx。把每个决策 j 看成平面上一个点：

x_j = s[j]
y_j = f[j] + s[j]²

把当前状态 i 看成一条斜率固定的直线：

k_i = 2·(L' - s[i])        （注意 s[i] 单调递增 → k_i 单调递减）

那么右边要最小化的正是 y_j - k_i·x_j——过点 j、斜率为 k_i 的直线的截距！

第三步：最优决策在下凸壳上

想象一条斜率为 k_i 的直线从下往上平移，第一个碰到的点就是使截距最小的点。显然这个点只可能在点集的下凸壳上（凸壳内部的点永远不会第一个被碰到）。于是：

不维护所有点，只维护下凸壳——凸壳上相邻两点连线的斜率从左到右严格递增；
本题中 s[i] 单调递增，所以斜率 k_i = 2(L'-s[i]) 单调递减；同时新点的横坐标 x_i = s[i] 单调递增，只会从右边插入。

这两条单调性合起来，意味着单调队列就够用，不需要二分或平衡树。

操作	条件（用乘法写）	含义
弹队首	`K(q[h],q[h+1]) ≤ k_i`	队首两点连线比直线平（或一样平），队首不可能最优
弹队尾	`K(q[t-1],q[t]) ≥ K(q[t],i)`	队尾点在新点加入后落到凸壳内部

完整代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int n; ll L;
    cin >> n >> L;
    vector<ll> c(n + 1);
    vector<ll> s(n + 1);          // s[i] = pre[i] + i（前缀和，含空隙）
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
        s[i] = s[i-1] + c[i] + 1; // 折叠：pre + i 等价于「(c+1) 的前缀和」
    }
    ll Lp = L + 1;
    vector<ll> f(n + 1);
    // 点 j：(x_j, y_j) = (s[j], f[j] + s[j]²)
    // 直线 i：斜率 k_i = 2(L' - s[i])，最小化截距 y_j - k_i·x_j
    // f[i] = min{ y_j - k_i·x_j } + (s[i] - L')²
    vector<int> q(n + 2);
    int head = 0, tail = 0;       // [head, tail)
    q[tail++] = 0;                // 决策点 0（f[0]=0, 点 (0,0)）入队
    auto X = [&](int j) { return s[j]; };
    auto Y = [&](int j) { return f[j] + s[j] * s[j]; };
    for (int i = 1; i <= n; i++) {
        ll k = 2 * (Lp - s[i]);   // 当前直线斜率（随 i 单调递减）
        // 弹队首：K(q[h],q[h+1]) <= k 时 q[h] 不可能是最优
        // 乘法形式：(Y[h+1]-Y[h]) <= k * (X[h+1]-X[h])
        while (tail - head >= 2) {
            ll dy = Y(q[head+1]) - Y(q[head]);
            ll dx = X(q[head+1]) - X(q[head]);
            if (dy <= k * dx) head++;
            else break;
        }
        int j = q[head];
        ll base = (s[i] - Lp) * (s[i] - Lp);
        f[i] = Y(j) + 2 * (Lp - s[i]) * s[j] + base;
        // 插入点 i：维护下凸壳（斜率严格递增）
        // 弹队尾：K(q[t-2],q[t-1]) >= K(q[t-1],i)，用叉积：
        while (tail - head >= 2) {
            int a = q[tail-2], b = q[tail-1];
            if ((Y(b) - Y(a)) * (X(i) - X(b)) >=
                (Y(i) - Y(b)) * (X(b) - X(a)))
                tail--;
            else break;
        }
        q[tail++] = i;
    }
    cout << f[n] << "\n";
    return 0;
}

手算核对（自造小数据）：

输入：
5 3
1 2 3 4 5

输出：
6

前缀 s = [0, 2, 5, 9, 14, 20]，L' = L + 1 = 4，转移为 f[i] = min{ f[j] + (s[i]-s[j]-4)² }。逐行填表（j = 0 表示「前面不分段」，即整个前缀作为一段）：

f[1] = f[0] + (2-0-4)²  = 4
f[2] = min(0+(5-0-4)², 4+(5-2-4)²) = min(1, 5) = 1        ← 决策 j=0
f[3] = min(0+(9-4)², 4+(9-2-4)², 1+(9-5-4)²) = min(25, 25, 1) = 1
f[4] = min(0+(14-4)², 4+(14-2-4)², 1+(14-5-4)², 1+(14-9-4)²)
     = min(100, 64, 26, 2) = 2                             ← 决策 j=3
f[5] = min(0+(20-4)², 4+(20-2-4)², 1+(20-5-4)², 1+(20-9-4)², 2+(20-14-4)²)
     = min(256, 196, 122, 50, 6) = 6                       ← 决策 j=4

与程序输出 6 一致。最优分段是 {1,2}{3}{4,5}：读者可以代入原代价公式 (段长+Σc-L)² 验证。

强烈建议： 斜率优化代码写完后，一定保留 O(N²) 暴力版本，用小随机数据对拍——本题的化简涉及 +1 折叠（L'=L+1）和平方展开，任何一处符号写错都会安静地输出错误答案。本书这两份代码正是通过对拍验证的。

何时可用（两个单调性都要检查）：

横坐标单调：新决策点的 x_i 随 i 递增（本题 x_i = s[i] 递增 ✓）→ 新点只会加在凸壳右端，队尾弹出即可；
斜率单调：查询斜率 k_i 随 i 单调（本题递减 ✓）→ 队首弹出的点永远不需要回来。

任一不满足，就要升级为「凸壳上二分」（斜率不单调）或 CDQ 分治 / 平衡树（横坐标不单调），复杂度变为 O(N log N) 或更差。

6.6.3 决策单调性（简介）

使用场景： 转移 f[i] = min{ w(j, i) } 中代价函数 w 满足四边形不等式，从而最优决策点 opt(i) 随 i 单调不减。

四边形不等式：「交叉小于包含」

若对所有 a ≤ b ≤ c ≤ d 都有

$$w(a,c) + w(b,d) \le w(a,d) + w(b,c)$$

则称 w 满足四边形不等式。直观记法：交叉 ≤ 包含（左边的区间「交叉」，右边的区间「包含」）。它的含义是：区间越大越「亏」，把小区间换成交叠区间总能更优。

定理（记住结论即可）： 若 w 满足四边形不等式，则 f(i) = min w(j,i) 的最优决策点 opt(i) 单调不减。

直觉：i 变大时，原来偏左的决策相对越来越差，最优决策只能右移。这正是「决策单调性」。

区间 DP 版本：石子合并

石子合并的区间 DP 是 dp[l][r] = min{ dp[l][k] + dp[k+1][r] } + cost(l,r)，其中 cost = 区间石子和。石子合并的代价满足四边形不等式（区间和关于「交叉/包含」满足该性质），因此最优分割点满足：

$$opt[l][r-1] \le opt[l][r] \le opt[l+1][r]$$

枚举 k 时只需在 [opt[l][r-1], opt[l+1][r]] 这个小区间里找。用 opt[l][r] 记录每个区间的最优分割点：

核心框架（决策单调性优化区间 DP）：

// opt[l][l] = l；l 从大到小、r 从小到大枚举
for (int l = n - 1; l >= 1; l--)
    for (int r = l + 1; r <= n; r++) {
        int lo = opt[l][r-1];              // 下界
        int hi = min(opt[l+1][r], r - 1);  // 上界
        ll best = LLONG_MAX; int bestk = lo;
        for (int k = lo; k <= hi; k++) {   // 只枚举小区间！
            ll cur = f[l][k] + f[k+1][r] + cost(l, r);
            if (cur < best) { best = cur; bestk = k; }
        }
        f[l][r] = best;
        opt[l][r] = bestk;
    }

内层循环的总长度从 O(N) 降为 O(opt 区间长度)，可以证明总复杂度为 O(N²)（原为 O(N³)），N = 5000 时约 2.5×10⁷，轻松通过。

一维版本的分治写法（f[i] = min{f[j] + w(j,i)} 型，如「分石子」类问题）也常考。设 DP(l, r, kl, kr) 表示要计算 f[l..r]，且这些状态的最优决策都在 [kl, kr] 中：

void DP(int l, int r, int kl, int kr) {
    if (l > r) return;
    int mid = (l + r) / 2, bestk = kl;
    // 暴力在 [kl, min(kr, mid-1)] 中找 f[mid] 的最优决策
    for (int j = kl; j <= min(kr, mid - 1); j++)
        if (w(j, mid) < w(bestk, mid)) bestk = j;
    f[mid] = w(bestk, mid);              // 或 f[j]+w 的形式
    // 由决策单调性，左右两半的决策区间被 bestk 切开
    DP(l, mid - 1, kl, bestk);
    DP(mid + 1, r, bestk, kr);
}

每层分治中决策区间总长度是 O(N)，共 O(log N) 层，总复杂度 O(N log N)。

完整代码（石子合并 + opt 区间优化）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int n;
    cin >> n;
    vector<ll> a(n + 1), pre(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pre[i] = pre[i-1] + a[i];
    }
    vector<vector<ll>> f(n + 2, vector<ll>(n + 2, 0));
    vector<vector<int>> opt(n + 2, vector<int>(n + 2, 0));
    if (n == 1) { cout << 0 << "\n"; return 0; }
    // opt[l][l] = l：单元素区间的「分割点」就是自己，
    // 保证后续 opt 下界不会取到 0（常见错误！）
    for (int l = 1; l <= n; l++) opt[l][l] = l;
    // 决策单调性：opt[l][r-1] <= opt[l][r] <= opt[l+1][r]
    for (int l = n - 1; l >= 1; l--) {
        for (int r = l + 1; r <= n; r++) {
            int lo = opt[l][r-1];
            int hi = min(opt[l+1][r], r - 1);
            int bestk = lo;
            ll best = LLONG_MAX;
            for (int k = lo; k <= hi; k++) {
                ll cur = f[l][k] + f[k+1][r] + pre[r] - pre[l-1];
                if (cur < best) { best = cur; bestk = k; }
            }
            f[l][r] = best;
            opt[l][r] = bestk;
        }
    }
    cout << f[1][n] << "\n";
    return 0;
}

样例：

输入：
4
1 2 3 4

输出：
19

手算：{1,2} 代价 3，{3,4} 代价 7，合并 {1,2} 和 {3,4} 代价 10；总计 3+7+10 = 20？再试 {1,2,3} 再并 4：{1,2}=3、{1,2,3}=6、总并=10，合计 19。✓ 最优是 19（f[1][2]=3, f[1][3]=3+6=9, f[4][4]=0，f[1][4] = f[1][3]+0+10 = 19）。

重要提醒： 决策单调性是一个需要**证明（或对拍验证）**的性质，不是所有区间 DP 都有。用之前先确认代价函数满足四边形不等式（石子合并、一些「区间染色」问题满足；带负权或奇怪代价的可能不满足）。

⚠️ DP 优化常见错误

展开——竞赛前必读

单调队列优化陷阱：

❌ 多重背包按余数分组时，y 的循环范围写成 0..W 而不是 0..min(w, W)——白做无用功，复杂度退化
❌ 队列里存的应是「变换后的 G 值对应的下标」，使用时忘记补回 - x·v + x·v，直接拿了错误的值
❌ 弹队首条件 < 与 <= 搞反——窗口长度 K+1 意味着 dq.front() < x - K 时才越界

斜率优化陷阱：

❌ 斜率比较用除法：(y2-y1)/(x2-x1) 有精度误差且可能除以 0——必须用乘法交叉相乘比较；乘积可能超 long long 时用 __int128
❌ 凸壳弹队条件方向写反：下凸壳（维护 min）弹队尾的条件是 K(队尾前, 队尾) ≥ K(队尾, 新点)；若写成 ≤ 会把凸壳上的合法点弹掉。记住口诀：下凸壳斜率要严格递增，「变平/变凹」就弹
❌ 弹队首与弹队尾的条件搞混：队首看的是查询斜率 k_i，队尾看的是新点与凸壳的斜率
❌ 忘记检查两个单调性前提（横坐标单调、查询斜率单调）就在不满足的题上套模板——会 WA
❌ 转移式化简时 +1、-1（如 L' = L+1）折错——斜率优化推导完必须用 O(N²) 暴力对拍

决策单调性陷阱：

❌ 石子合并的 opt[l][l] 初始化为 0 而不是 l——opt[l][r-1] 当 r-1=l 时会取到 0，导致 k 从 0 枚举（越界）或漏算
❌ 没验证代价函数满足四边形不等式就乱套——决策不单调的题会得到错误答案
❌ 分治写法中 min(kr, mid-1) 忘记加——决策点 j 必须 < mid（j 是 mid 的左决策）

本章总结

📌 模式识别指南

优化技术	转移式的样子	关键性质	复杂度	代表题
单调队列	`dp[i] = max{ dp[j] + g(j) }`，j 在平移窗口内	窗口最值	O(N·W·k) → O(N·W)	多重背包
斜率优化	`dp[i] = min{ dp[j] + (s_i-s_j)² }` 等含乘积项	决策是点、转移是直线截距；横坐标与斜率均单调	O(N²) → O(N)	玩具装箱
决策单调性	`dp[i] = min{ w(j,i) }`，w 满足四边形不等式	opt(i) 单调不减	O(N²) → O(N log N)（分治）或 O(N³) → O(N²)（区间）	石子合并

🧩 核心框架速查

// 单调队列优化：窗口 [i-K, i] 的最值
deque<int> dq;
for (int i = 0; i < n; i++) {
    while (!dq.empty() && dq.front() < i - K) dq.pop_front();
    while (!dq.empty() && val(dq.back()) <= val(i)) dq.pop_back();
    dq.push_back(i);
    // dq.front() 是窗口 [i-K, i] 内 val 最大的下标
}

// 斜率优化：下凸壳 + 单调队列（横坐标、查询斜率均单调）
// 弹队首：K(q[h],q[h+1]) <= k_i → 用 (Y[h+1]-Y[h]) <= k*(X[h+1]-X[h])
// 弹队尾：K(q[t-2],q[t-1]) >= K(q[t-1],i) → 交叉相乘比较
// f[i] = min{ Y[j] - k_i*X[j] } + (只与 i 有关的项)

// 决策单调性分治：DP(l, r, kl, kr)
void DP(int l, int r, int kl, int kr) {
    if (l > r) return;
    int mid = (l + r) / 2, bestk = kl;
    for (int j = kl; j <= min(kr, mid - 1); j++)
        if (w(j, mid) < w(bestk, mid)) bestk = j;
    f[mid] = w(bestk, mid);
    DP(l, mid - 1, kl, bestk);
    DP(mid + 1, r, bestk, kr);
}

❓ 常见问题

Q1：我怎么判断一道题该用哪种优化？

A：先写朴素转移式，然后看它的形状：(1) 候选 j 构成平移的固定窗口 → 单调队列；(2) 展开后出现 s[i]·s[j] 之类的乘积项、能整理成 y_j - k_i·x_j → 斜率优化；(3) 代价函数满足「交叉小于包含」→ 决策单调性。三者互相不排斥，同一道题可能先后用到多种。

Q2：斜率优化里为什么比较斜率一定要用乘法（交叉相乘）？

A：两个原因：一是除法有浮点精度误差，在 s[i] 达 10⁹ 级别时足以判错方向；二是 x2 - x1 可能为 0（除零）。交叉相乘把比较变成整数乘法，没有精度问题。注意乘积范围：(10⁷+10⁵)² × (10⁷+10⁵)² 会超 long long，此时用 __int128 存中间乘积。

Q3：斜率优化的两个单调性不满足怎么办？

A：分情况。横坐标单调但查询斜率不单调：在凸壳上二分找切点，O(N log N)。横坐标不单调：CDQ 分治或平衡树（如李超树）维护凸壳。这些属于更进阶的内容，NOIP/USACO Silver-Gold 层面掌握「双单调 + 单调队列」版本即可。

练习题

题目 6.6.1 — 单调队列优化：跳房子（洛谷 P1725） 🟡 中等数轴上 0..n 每个整数点有一个格子，格 i 有分值 s_i（可负）。你从 0 出发只能向右跳，每次跳跃距离必须在 [L, R] 内。跳到（或越过——本题要求恰好落在格子上）任意格子的得分累加，求能获得的最大总得分；若无法继续跳跃则结束，得分可以为负无穷时输出 -1。n ≤ 5×10⁵。

提示

`dp[i]` = 到达格 i 的最大得分。转移 `dp[i] = s_i + max{ dp[j] : i-R ≤ j ≤ i-L }`——固定长度窗口最大值，单调队列。不满足则 dp 值为负无穷。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; long long L, R;
    // 洛谷 P1725 格式：第一行 n, L1, R1（L1+R1 为跳跃距离区间）
    cin >> n >> L >> R;
    vector<long long> s(n + 1);
    for (int i = 0; i <= n; i++) cin >> s[i];
    const long long NEG = LLONG_MIN / 4;
    vector<long long> dp(n + 1, NEG);
    deque<int> dq;                    // 存下标，dp 值单调递减
    dp[0] = s[0];
    for (int i = 1; i <= n; i++) {
        // 新可用的决策下标是 i - L（跳 [L,R]，从 j 跳到 i 需 i-j ∈ [L,R]）
        int j = (int)(i - L);
        if (j >= 0 && dp[j] > NEG) {
            while (!dq.empty() && dp[dq.back()] <= dp[j]) dq.pop_back();
            dq.push_back(j);
        }
        while (!dq.empty() && dq.front() < i - R) dq.pop_front();
        if (!dq.empty()) dp[i] = dp[dq.front()] + s[i];
    }
    long long ans = NEG;
    for (int i = n; i >= 0 && n - i <= R; i--) ans = max(ans, dp[i]);
    cout << (ans <= NEG / 2 ? -1 : ans) << "\n";
    return 0;
}

复杂度： O(K)，每个下标入队出队各一次。

题目 6.6.2 — 斜率优化：仓库建设（ZJOI2007） 🔴 困难一条直线上有 n 个工厂，工厂 i 距离起点 x_i（递增），有 p_i 件货物，建仓库的花费为 C_i。货物可以往右运到下一个「已建仓库的工厂」，运输单价 1，即把工厂 i 的货物运到工厂 j 的花费是 p_i·(x_j - x_i)。每个工厂的货物要么就地建仓，要么运到右边最近的仓库。求最小总花费。n ≤ 10⁶。

提示

`f[i]` = 前 i 个工厂都处理完、工厂 i 建了仓库的最小花费。设 `sp` 为 p 前缀和、`spx` 为 `p·x` 前缀和： `f[i] = C_i + min{ f[j] + Σ_{k=j+1..i} p_k·(x_i - x_k) }` `= C_i + x_i·(sp_i - sp_j) - (spx_i - sp_j 前的项) + ...` 展开后整理成 `y_j - k_i·x_j` 的形式，其中 `k_i = x_i` 单调递增、横坐标也单调——标准斜率优化。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int n;
    cin >> n;
    vector<ll> x(n+1), p(n+1), C(n+1), sp(n+1, 0), spx(n+1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> p[i] >> C[i];
        sp[i] = sp[i-1] + p[i];
        spx[i] = spx[i-1] + p[i] * x[i];
    }
    vector<ll> f(n+1);
    // f[i] = C[i] + x_i*(sp_i - sp_j) - (spx_i - spx_j) + f[j]
    //      = (f[j] + spx[j]) - x_i * sp[j] + (C[i] + x_i*sp_i - spx_i)
    // 点 j：(x_j, y_j) = (sp[j], f[j] + spx[j])；斜率 k_i = x_i（递增）
    vector<int> q(n+2);
    int head = 0, tail = 0;
    q[tail++] = 0;
    auto X = [&](int j) { return sp[j]; };
    auto Y = [&](int j) { return f[j] + spx[j]; };
    for (int i = 1; i <= n; i++) {
        ll k = x[i];
        // 弹队首：K(q[h],q[h+1]) <= k（插入端已保证横坐标严格递增）
        while (tail - head >= 2) {
            ll dy = Y(q[head+1]) - Y(q[head]);
            ll dx = X(q[head+1]) - X(q[head]);
            if (dy <= k * dx) head++;
            else break;
        }
        int j = q[head];
        f[i] = Y(j) - k * X(j) + C[i] + x[i] * sp[i] - spx[i];
        // 插入点 i：若与队尾横坐标相同（p_i=0 时 sp 不变），只保留 y 更小者
        bool insert = true;
        while (tail - head >= 1 && X(i) == X(q[tail-1])) {
            if (Y(i) < Y(q[tail-1])) tail--;
            else { insert = false; break; }
        }
        if (insert) {
            while (tail - head >= 2) {
                int a = q[tail-2], b = q[tail-1];
                if ((Y(b)-Y(a)) * (X(i)-X(b)) >=
                    (Y(i)-Y(b)) * (X(b)-X(a)))
                    tail--;
                else break;
            }
            q[tail++] = i;
        }
    }
    // 最后一个仓库必须建在工厂 n（否则它右边的货物无处可运），
    // 所以答案就是 f[n]
    cout << f[n] << "\n";
    return 0;
}

复杂度： O(N)。⚠️ 本题推导链较长：先把「区间 [j+1, i] 的运输总花费」用前缀和 sp、spx 表示，再按「只与 j 有关 / 只与 i 有关 / 与两者都有关」三组整理，最后识别出 k_i = x_i（单调递增）与 x_j = sp[j]（单调递增）——两个单调性都成立，标准单调队列版斜率优化即可。另注意一个细节：p_i = 0 时相邻两点横坐标相同，插入时只保留 y 更小的点，否则凸壳上会出现竖直边，弹队首时 dx = 0 会让斜率比较判错方向。

题目 6.6.3 — 决策单调性：石子合并变体（能量项链式合并） 🟡 中等 N 堆石子（N ≤ 5000）排成一行，合并相邻两堆的代价为两堆石子数之和的平方。求最小总代价。区间的「代价函数」cost² 仍满足四边形不等式吗？先用 O(N³) 暴力对拍验证你的决策单调性优化是否正确。

提示

`f[l][r] = min{ f[l][k]+f[k+1][r] } + (pre[r]-pre[l-1])²`。代价只与区间和有关，仍满足四边形不等式（凸函数的复合保持性质），opt 区间优化照常适用；但对拍是必须的——平方后的代价结构变了，别想当然。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int n;
    cin >> n;
    vector<ll> a(n + 1), pre(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pre[i] = pre[i-1] + a[i];
    }
    vector<vector<ll>> f(n + 2, vector<ll>(n + 2, 0));
    vector<vector<int>> opt(n + 2, vector<int>(n + 2, 0));
    if (n == 1) { cout << 0 << "\n"; return 0; }
    for (int l = 1; l <= n; l++) opt[l][l] = l;
    for (int l = n - 1; l >= 1; l--)
        for (int r = l + 1; r <= n; r++) {
            int lo = opt[l][r-1], hi = min(opt[l+1][r], r - 1);
            ll sum = pre[r] - pre[l-1];
            ll best = LLONG_MAX; int bestk = lo;
            for (int k = lo; k <= hi; k++) {
                ll cur = f[l][k] + f[k+1][r] + sum * sum;
                if (cur < best) { best = cur; bestk = k; }
            }
            f[l][r] = best;
            opt[l][r] = bestk;
        }
    cout << f[1][n] << "\n";
    return 0;
}

复杂度： O(N²)，N = 5000 时约 2.5×10⁷ 次操作，轻松通过。

💡 下一步： DP 优化是「转移式形状分析」的训练——每次都先把朴素转移写在纸上，看它的候选结构（窗口？点集？单调决策？），再选工具。第七部分图论中的最短路（Dijkstra）也会遇到完全相同的「冗余决策剔除」思想。

C++ 竞赛编程：USACO 学习指南

第 6.6 章：DP 优化

6.6.0 从三道超时的题出发

6.6.1 单调队列优化

例题：多重背包

完整代码

6.6.2 斜率优化

例题：玩具装箱（HNOI2008）

第一步：化简——消掉式子里的 i 和 j

第二步：拆平方，按「与谁有关」分组

第三步：最优决策在下凸壳上

第四步：单调队列维护凸壳

完整代码

6.6.3 决策单调性（简介）

四边形不等式：「交叉小于包含」

区间 DP 版本：石子合并

完整代码（石子合并 + opt 区间优化）

⚠️ DP 优化常见错误

本章总结

📌 模式识别指南

🧩 核心框架速查

❓ 常见问题

练习题