分治优化决策单调DP

当 Q_(i,j) (f(j))=w(i,j) 与 f(j) 无关且最优决策点满足决策单调性时,按中点扫描候选区间并递归,以 O(n log n) 求出全部 f(i)。

时间 O(n log n),空间 O(n) · 标签 动态规划 / 决策单调性 / 分治 / DP 优化

问题形式

考虑 1D/1D 动态规划中,当 𝑄𝑖,𝑗(𝑓(𝑗))=𝑤(𝑖,𝑗) 与 𝑓(𝑗) 无关,且最优决策点满足 决策单调性 时,方程退化为

𝑓(𝑖)=min𝐿(𝑖)≤𝑗≤𝑅(𝑖)𝑤(𝑖,𝑗).

其中 1≤𝐿(𝑖)≤𝑅(𝑖)<𝑖。因为 𝑤 不含 𝑓(𝑗),𝑓(𝑖) 的值不受其他 𝑓 的影响,计算顺序可以任意;转移范围仍按 𝑖 的定义。

核心思想

记 solve(𝑙,𝑟,𝐿,𝑅) 计算 𝑓(𝑙),…,𝑓(𝑟),并已知这些状态的最优决策都在 [𝐿,𝑅]。

取 𝑚=⌊𝑙+𝑟2⌋,在 [max(𝐿,𝐿(𝑚)),min(𝑅,𝑅(𝑚))] 中扫描,求出 𝐽(𝑚),再计算

𝑓(𝑚)=𝑤(𝑚,𝐽(𝑚)).

递归计算 solve(𝑙,𝑚−1,𝐿,𝐽(𝑚)) 和 solve(𝑚+1,𝑟,𝐽(𝑚),𝑅)。初始调用为 solve(1,𝑛,1,𝑛)。

分治树每层扫描的候选区间总长为 𝑂(𝑛),共 𝑂(log𝑛) 层,因此总时间为 𝑂(𝑛log𝑛)。

正确性

分治的不变式是:进入 solve(𝑙,𝑟,𝐿,𝑅) 时,任意 𝑖∈[𝑙,𝑟] 的 𝐽(𝑖) 都在 [𝐿,𝑅] 内。

取 𝑚 后,扫描范围包含 [𝐿(𝑚),𝑅(𝑚)] 与 [𝐿,𝑅] 的交,因此能找到 𝐽(𝑚)。由 𝐽 单调,左半部分满足 𝐽(𝑖)≤𝐽(𝑚),右半部分满足 𝐽(𝑖)≥𝐽(𝑚),递归范围正确。

由于 𝑄𝑖,𝑗 与 𝑓(𝑗) 无关,计算 𝑓(𝑚) 不需要左侧的 𝑓(𝑗),所以可以先算 𝑚 再递归。归纳得所有 𝑓(𝑖) 正确。

易错点

  • 𝑄𝑖,𝑗 依赖 𝑓(𝑗) 时不能用本页分治:计算 𝑓(𝑚) 时,左侧的 𝑓(𝑗) 可能尚未计算。
  • 扫描范围要取 [𝐿(𝑚),𝑅(𝑚)] 与 [𝐿,𝑅] 的交,不能漏掉端点。
  • 分治是 𝑂(𝑛log𝑛),不是 𝑂(𝑛);每层都要扫描候选。
源码位置