第 104 章　DP 优化¶

配套例题：BISHI146 收集金币、BISHI147 旅行者的大逃脱、BISHI121 数列后缀极大位置统计来源：S3 day6/DP资料/进阶资料/动规问题的优化.md、浅析1D1D动态规划的优化.md、单调队列.md、S4 模板.docx（矩阵乘法）

DP 优化有两条完全不同的路线，先分清再学具体技巧：

路线	做什么	本章位置
降低渐进复杂度	用数据结构或数学性质加速转移	104.1 – 104.5
消掉一维状态	重新建模，让某一维状态根本不需要存在	104.6

在 Python 里还有第三条路线——把循环下沉到 C 层（不改复杂度，只改常数），它已在前面各章反复出现，本章 104.7 做统一总结。

104.1　单调队列优化¶

适用形式¶

\[ f_i = \min_{i - k \le j < i}\big(f_j + w(i)\big) \]

转移的候选集合是一个滑动窗口，且 \(w\) 只依赖 \(i\)（与 \(j\) 无关）。这时用单调队列维护窗口最小值，把每次 \(O(k)\) 的枚举降到均摊 \(O(1)\)。

# [片段]
from collections import deque

dq = deque()                          # 存下标，对应的 f 值单调递增
for i in range(1, n + 1):
    while dq and dq[0] < i - k:       # 弹出滑出窗口的：队首下标必须落在 [i-k, i-1] 内
        dq.popleft()
    f[i] = f[dq[0]] + w(i) if dq else INF   # 队首即窗口最小值，取答案要在弹尾之前
    while dq and f[dq[-1]] >= f[i]:   # 维护单调性：比新来的还大的旧值永远轮不到它
        dq.pop()                      # 用 >= 而非 >，相等的旧下标先过期，留着没用
    dq.append(i)                      # i 本身要作为后续位置的候选入队

三个必须做对的细节¶

队列里存下标而不是值，否则无法判断是否滑出窗口。

先弹队首（过期），再取答案，最后弹队尾（维护单调）。顺序错了会取到过期值。

弹队尾的条件用 >= 还是 >：求最小值时用 >=（相等的旧下标留着没用，弹掉更省）。

与多重背包的关系¶

多重背包按 \(j \bmod w\) 分组后，组内转移正好是滑动窗口最大值，可以做到 \(O(nm)\)。 BISHI138 正是靠它才过的，见 101-背包问题 §101.5。

这里有个很容易想反的地方。 单调队列每一步都是 Python 层操作，二进制拆分每一轮却是 C 层整段处理，看上去后者更适合 Python；但极限数据下二进制拆分 80.1 秒、单调队列 14.9 秒，后者快 5.4 倍。因为拆分把物品数放大了约一个数量级，C 层的常数优势补不回多出来的那个 \(\log\)。

正确的次序是：先看渐进复杂度，再谈常数。 「把循环压进 C 层」是常数优化，它能救的是同复杂度下的实现差距，救不了复杂度本身高一个 \(\log\) 的算法。 39 章的 BISHI130 是同一条原则在数据结构上的另一面：那里换 PyPy 都救不回分块，只能改线段树。

单调队列本身见 37-单调栈与单调队列。

104.2　前缀和优化¶

适用形式¶

\[ f_i = \sum_{j \in [l_i,\ r_i]} f_j \]

转移是一段连续区间的和。维护 \(f\) 的前缀和 \(S\)，每次 \(O(1)\) 取出。

# [片段]
from itertools import accumulate

# 注意：S 必须是「上一层」f 的前缀和，边算边更新时要小心依赖
S = [0] + list(accumulate(f))         # S[i] = f[0] + ... + f[i-1]；前面补 0 省掉边界判断
# 闭区间 [l, r] 的和 = S[r+1] - S[l]，右端点要加一才落到「前缀和」的下标约定上
f_new = [(S[r + 1] - S[l]) % MOD for l, r in ranges]

accumulate 是 C 实现，这一步几乎免费。

二维版本¶

\(f[i][j]\) 依赖上一行的一段区间和 ⇒ 对每一行做前缀和。若依赖的是一个矩形区域，用二维前缀和的四项容斥，见 42-前缀和与差分。

BISHI147 用的就是「带重置的前缀和」¶

网格里每时刻只能向下或向右走任意正整数步，检查官从指定时刻起永久占据格子，求最短逃脱时刻与总方案数。\(n, m \le 500\)，\(k \le 100\)。

朴素转移要枚举「走几步」，\(O(n+m)\)；用前缀和降到 \(O(1)\)。但因为被占据的格子会打断一次移动，所以是「带重置的前缀和」—— 遇到不可通行的格子就把累加值清零。

# [片段]
# 一次移动必须落在同一段连续可通行区间内，所以按「段」做 accumulate
for s, e in runs:                     # runs 是这一行/列的极大可通行区间，左闭右开
    acc = list(accumulate(dp[s:e]))   # 只在段内累加，跨过障碍就自动从头开始
    # 目标位置 b 的候选和 = acc[b - s - 1]
    # 减 s 是把绝对下标换成段内下标，再减 1 是因为「必须走至少一步」，不含 b 自己

Python 关键技巧：把 DP 数组存成一维扁平数组，这样

第 \(x\) 行是 dp[x*m : (x+1)*m] —— 连续切片
第 \(y\) 列是 dp[y::m] —— 步长切片

两者都能直接喂给 accumulate，行和列的前缀和都能走 C 层。如果按「二维列表」存，列方向就必须逐行取元素，退化成 Python 层循环。

⚠️ 本题在 CPython 下必然 TLE，必须用 PyPy3 提交。 状态数 \(k \cdot n \cdot m = 2.5\times10^7\)，5 组数据共 \(1.25\times10^8\)；每个时刻还要对 250000 个元素做一次 Python 层取模。 本机实测极限数据 30.8 秒，限时 4 秒。 C++ 同思路约 0.3 秒。这不是实现没优化到位，而是纯 CPython 的物理下限。

但「CPython 过不去」不等于「这题做不了」：换成 PyPy3（牛客语言 id 25）同一份代码一次通过。上面那些「把前缀和压进 accumulate、用一维扁平数组让行列都能切片」的优化仍然值得做—— PyPy 也吃这套，只是它把剩下的 Python 层循环也一并 JIT 掉了。提交语言登记在 solutions/_lang.json。

题解：solutions/BISHI147.py（已通过牛客判题机验证，PyPy3）

104.3　矩阵快速幂加速线性递推¶

适用形式¶

\[ f_i = c_1 f_{i-1} + c_2 f_{i-2} + \cdots + c_d f_{i-d} \]

系数与 \(i\) 无关（常系数齐次线性递推），且 \(n\) 极大（\(10^{12}\) 甚至 \(10^{18}\)）。

把递推写成矩阵乘法，用快速幂算 \(M^n\)，复杂度 \(O(d^3 \log n)\)。

斐波那契的转移矩阵：

\[ \begin{pmatrix} f_{i} \\ f_{i-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} f_{i-1} \\ f_{i-2} \end{pmatrix} \]

# [片段]
def mat_mul(A, B, mod):
    n, m, p = len(A), len(B), len(B[0])
    # zip(*B) 一次转置，内层用 sum(map(mul, ...)) 走 C 层
    BT = list(zip(*B))                # 转置后「取 B 的第 j 列」变成「取 BT 的第 j 行」
    # 结果的第 (i, j) 项 = A 第 i 行与 B 第 j 列的点积，最后统一取模
    return [[sum(a * b for a, b in zip(row, col)) % mod for col in BT]
            for row in A]


def mat_pow(M, e, mod):
    n = len(M)
    R = [[int(i == j) for j in range(n)] for i in range(n)]   # 单位矩阵
    while e:                          # 把指数 e 按二进制位从低到高处理
        if e & 1:                     # 当前位是 1，就把对应的 M 的幂乘进答案
            R = mat_mul(R, M, mod)
        M = mat_mul(M, M, mod)        # M 每轮自乘，依次代表 M 的 1、2、4、8 次幂
        e >>= 1                       # 右移一位 = 处理下一个二进制位
    return R

Python 优化点：zip(*B) 转置一次，避免内层反复按列取元素； sum(a*b for ...) 比显式 for 累加快。但矩阵乘法本身是 \(O(d^3)\) 的三重循环，\(d\) 大于 10 左右在 Python 里就吃力了。

什么时候用、什么时候不用¶

\(n\) 的范围	做法
\(n \le 10^7\)	直接线性递推（\(O(n)\)），Python 里比矩阵快
\(n \ge 10^9\)	矩阵快速幂
递推阶数\(d \ge 20\)	矩阵乘法\(O(d^3\log n)\) 也吃不消，考虑多项式取模（Kitamasa / BM）

BISHI131 数楼梯的 \(n \le 10^5\)，用不着矩阵快速幂——直接递推更快更简单。见 100-DP入门。斐波那契的快速倍增写法见 85-基础数学与递推。

104.4　决策单调性¶

适用形式¶

\[ f_i = \min_{j < i}\big(f_j + w(j, i)\big) \]

设 \(\text{opt}(i)\) 为使 \(f_i\) 取到最优的 \(j\)。若

\[ i_1 < i_2 \implies \text{opt}(i_1) \le \text{opt}(i_2) \]

则称转移具有决策单调性。此时可以用分治或单调栈（二分队列）把 \(O(n^2)\) 降到 \(O(n\log n)\)。

判定：四边形不等式¶

若 \(w\) 满足

\[ w(a, c) + w(b, d) \le w(a, d) + w(b, c) \qquad (a \le b \le c \le d) \]

则决策单调性成立。这个条件叫四边形不等式（也称凸完全单调性）。

实战中怎么用：笔试时不必严格证明。先写 \(O(n^2)\) 暴力，打表输出 \(\text{opt}(i)\) 序列，看它是否单调递增。单调就大胆用，这是 S3 课件《动规问题的优化》里推荐的做法。

分治实现¶

# [片段]
def solve(lo, hi, opt_lo, opt_hi):
    """计算 f[lo..hi]，已知它们的最优决策落在 [opt_lo, opt_hi]。"""
    if lo > hi:
        return                              # 区间为空，递归到底
    mid = (lo + hi) // 2                    # 先算中点，它的决策把候选区间劈成两半
    best, best_j = INF, opt_lo
    # 决策只可能落在 [opt_lo, opt_hi] 内，且不能超过 mid 本身
    for j in range(opt_lo, min(mid, opt_hi) + 1):
        v = f[j] + w(j, mid)
        if v < best:                        # 严格小于才更新，同优时留下标更小的
            best, best_j = v, j
    f[mid] = best
    solve(lo, mid - 1, opt_lo, best_j)      # 左半的决策不超过 best_j
    solve(mid + 1, hi, best_j, opt_hi)      # 右半的决策不小于 best_j

递归深度只有 \(O(\log n)\)，Python 里完全安全（不像树形 DP）。总枚举量 \(O(n\log n)\)。

这与 118-分治进阶的整体二分是同一族思想： 利用单调性把「每个询问独立二分」压成「一次分治处理全部询问」。

104.5　斜率优化（凸包优化）¶

适用形式¶

\[ f_i = \min_j\big(f_j + (\text{只含 } i \text{ 的项}) + (\text{只含 } j \text{ 的项}) + (\text{交叉项 } a_i \cdot b_j)\big) \]

关键特征是存在 \(i\) 与 \(j\) 的乘积项。把式子整理成

\[ f_j + (\text{只含 }j) = a_i \cdot b_j + (f_i - \text{只含 }i) \]

看成平面上的点 \((b_j,\ f_j + \text{只含 }j)\) 与斜率 \(a_i\) 的直线—— 求最小值就是求这些点的下凸壳上被斜率 \(a_i\) 切到的点。

用单调队列维护凸壳，总复杂度 \(O(n)\)（\(a_i\) 单调时）或 \(O(n\log n)\)（需二分时）。

经典例题（S3 课件里的）¶

题目	特征
玩具装箱（HNOI2008）	最基础的斜率优化，\(a_i\) 单调
土地购买（USACO 2008）	先排序去支配点，再斜率优化
货币兑换（NOI2007）	\(a_i\) 不单调 ⇒ 需要平衡树/CDQ 维护动态凸壳

⚠️ Python 现实性判断：斜率优化的每一步都是 Python 层的浮点/整数比较，且要维护队列。\(n = 10^5\) 时约 \(10^6\) 次 Python 操作，勉强可行； \(n = 10^6\) 就不行了。而且斜率比较务必用交叉相乘而不是除法—— 浮点误差会让凸壳判断出错，这是斜率优化最经典的 WA 来源：
# [片段]
# ❌ (y2-y1)/(x2-x1) < (y3-y2)/(x3-x2)      浮点误差
# ✅ (y2-y1)*(x3-x2) < (y3-y2)*(x2-x1)      整数交叉相乘
# 两个分母都为正时不等号方向不变，交叉相乘后全程整数，Python 大整数还不会溢出

本教程不展开完整实现——它属于省选难度，且题单里没有对应题目。 1D1D 优化的完整分类见 S3 课件 sources/02-oi-courseware/day6/DP资料/进阶资料/浅析1D1D动态规划的优化.md。

104.6　最有效的优化：消掉一维状态¶

前面五种技巧都是「加速转移」，而这一节是「让状态根本不存在」。 后者往往更有效，也更常出现在笔试里。

BISHI146 收集金币（中等）¶

网格里只能向右/向下走，格子 \((x,y)\) 会在第 \(v\) 回合变墙，求能收集的最多金币。 \(n, m \le 1000\)。

朴素想法：状态里带上「当前回合数」，\(f[r][i][j]\)，\(O(nm(n+m))\) 直接爆炸。

观察：只能右/下走 ⇒ 第 \(r\) 回合结束时必然站在 \(i + j - 2 = r\) 的那条反对角线上。也就是说，格子 \((i,j)\) 只会在第 \(r = i+j-2\) 回合被访问。于是

\[ (i,j) \text{ 可用} \iff v(i,j) > i + j - 2 \]

时间维直接消失了。 剩下的就是最朴素的网格路径最大权和：

\[ f[i][j] = a[i][j] + \max\big(f[i-1][j],\ f[i][j-1]\big) \]

坑：

答案不是 \(f[n][m]\)，而是所有可达格子里 \(f\) 的最大值—— 他可以随时被堵住而停下，不必走到右下角。样例 2 的答案就是只站在起点的 1。

判定条件的等号：\(v > i+j-2\)（严格大于），写成 \(\ge\) 会多用一个已经变墙的格子。

「不可达」要和「金币数 0」区分开（\(a_{ij} \ge 1\)，所以用 \(-1\) 当不可达哨兵是安全的）。

读入 \(10^6\) 个整数 + \(10^6\) 次 DP 迭代，时限「其他语言 2 秒」—— 必须一次性 read().split()，DP 用局部变量缓存行引用，才有希望。只有 \(t\) 个格子有变墙信息，其余永不变墙，用一个 bytearray 标记即可。

题解：solutions/BISHI146.py（已通过官方样例验证）

BISHI135 的坐标系变换¶

同样的思路：把「\(|l-r| \le k\)」这个看似需要一维状态的约束，换个坐标系后变成「终点列号落在某个区间内」。见 102-线性DP §102.5。

识别信号¶

题目里出现	尝试
「第\(r\) 回合/时刻」+ 移动方向受限	位置能否唯一决定时刻？（反对角线、层数）
「两个计数之差有界」	换坐标系变成位置的范围约束
「至多用一次某种操作」	加一维 0/1，而不是加一维计数
「模\(k\) 余 \(r\)」「和为偶数」	先想同余/奇偶的结构性质，可能连 DP 都不用（BISHI44）

BISHI121 是这个思路的极致：「所有后缀最大值下标的集合」被识别成 单调递减栈本身，于是根本不需要 DP——每次操作只要弹栈压栈，\(O(n)\) 解决。见 37-单调栈与单调队列。题解：solutions/BISHI121.py（已通过官方样例验证）

104.7　Python 专属：把循环下沉到 C 层¶

这条不改变复杂度，但在 Python 里往往比换算法更管用。前面各章的实例汇总：

场景	下沉写法	出处
01 背包整段取 max	`f[v:] = list(map(max, f[v:], [x+w for x in f[:V+1-v]]))`	101 章
完全背包	二进制倍增，每轮一次上面的整段取 max	101 章
二维费用背包	内层整行批处理	101 章
分组背包	每组一个`tmp`，候选取自旧 `f`	101 章
区间 DP 枚举断点	维护转置表 +`min(map(add, 行切片, 列切片))`	103 章
前缀和	`itertools.accumulate`	104.2
行/列前缀和	一维扁平数组 + `dp[xm:(x+1)m]` / `dp[y::m]`	104.2（BISHI147）
ST 表建表	`list(map(max, prev, prev[half:]))`	45-倍增
超 64 位集合运算	Python 大整数当 bitset	116 章

核心心法：Python 优化不是让循环跑得更快，而是让循环消失。 \(O(\sqrt n)\) 的 C 层操作常常打得过 \(O(\log^2 n)\) 的 Python 层操作。

104.8　优化决策树¶

DP 写完发现超时，按这个顺序排查：

状态数本身是否过大？ 若 \(> 10^7\)，先想能不能消掉一维（104.6）——这是收益最高的。
转移是否可以 \(O(1)\)？ 是滑动窗口 ⇒ 单调队列；是区间和 ⇒ 前缀和。
内层循环能否下沉到 C 层？（104.7）Python 专属，收益 5–8 倍。
\(n\) 是否极大而阶数很小？ ⇒ 矩阵快速幂。
决策点是否单调？ 打表验证 \(\text{opt}(i)\) ⇒ 分治优化。
是否有 \(i \cdot j\) 交叉项？ ⇒ 斜率优化（Python 下慎用）。
以上都不行 ⇒ 这题在 Python 下可能无解。如实标注，不要假装能过。见附录 C。

104.9　本章速查¶

优化	适用形式	复杂度	Python 可行规模
单调队列	转移候选是滑动窗口	\(O(n)\)	\(10^6\) ✅
前缀和	转移是区间和	\(O(1)\) / 次	\(10^6\) ✅（`accumulate`）
矩阵快速幂	常系数线性递推、\(n\) 极大	\(O(d^3\log n)\)	\(d \le 10\) ✅
决策单调性 + 分治	满足四边形不等式	\(O(n\log n)\)	\(10^5\) ✅（递归深度只有 \(\log n\)）
斜率优化	有\(a_i b_j\) 交叉项	\(O(n)\)	\(10^5\) ⚠️、\(10^6\) ❌
消掉一维状态	位置能唯一决定时刻等	降一个数量级	收益最高，优先考虑
下沉到 C 层	任何整段可批处理的转移	常数 ÷ 5~8	Python 专属

陷阱	正解
单调队列存值不存下标	存下标才能判是否滑出窗口
单调队列三步顺序错	先弹队首过期 → 取答案 → 再弹队尾
斜率优化用除法比较	整数交叉相乘，浮点误差会毁掉凸壳
\(n \le 10^5\) 上矩阵快速幂	直接线性递推更快
多重背包用二进制拆分	极限数据 80.1 秒；单调队列 14.9 秒。先比复杂度，再谈常数
BISHI146 输出\(f[n][m]\)	答案是全局最大值，他可以中途被堵住
明知会 TLE 却不说	如实标注，诚实标注比虚假全绿有价值

第 104 章 DP 优化¶

104.1 单调队列优化¶

适用形式¶

三个必须做对的细节¶

与多重背包的关系¶

104.2 前缀和优化¶

适用形式¶

二维版本¶

BISHI147 用的就是「带重置的前缀和」¶

104.3 矩阵快速幂加速线性递推¶

适用形式¶

什么时候用、什么时候不用¶

104.4 决策单调性¶

适用形式¶

判定：四边形不等式¶

分治实现¶

104.5 斜率优化（凸包优化）¶

适用形式¶

经典例题（S3 课件里的）¶

104.6 最有效的优化：消掉一维状态¶

BISHI146 收集金币（中等）¶

BISHI135 的坐标系变换¶

识别信号¶

104.7 Python 专属：把循环下沉到 C 层¶

104.8 优化决策树¶

104.9 本章速查¶

第 104 章　DP 优化¶

104.1　单调队列优化¶

104.2　前缀和优化¶

104.3　矩阵快速幂加速线性递推¶

104.4　决策单调性¶

104.5　斜率优化（凸包优化）¶

104.6　最有效的优化：消掉一维状态¶

104.7　Python 专属：把循环下沉到 C 层¶

104.8　优化决策树¶

104.9　本章速查¶