决策单调的分治 DP 优化

分治公理库分治法Divide and conquer把问题分成较小同类子问题，递归求解后合并结果的算法设计范式。在这里先问中间终点应该在哪里切。如果它的最佳切点是 $p$，左边状态的最佳切点不能越过 $p$，右边状态的最佳切点不能退到 $p$ 左边。一次完整扫描换来了两片可以永久跳过的候选区。

正确性沿递归树归纳。根结点的候选范围包含全部合法切点；父结点扫描得到真正的中间最优解，单调性保证两个孩子收紧后的范围仍包含各自真解。每一层都保持这个不变量，叶子因此也正确。统一取最左最优切点，使边界 $p$ 在平局时有确定含义。

十二项工作量的第二层 ​

取

前缀和为

费用 $C(k,j)=(S_j-S_k{)}^2$。第一层只有切点零，所以 $D_1[j]=S_j^2$。第二层首次处理终点 $j=2,\dots ,12$，中点为 $7$，扫描切点 $1,\dots ,6$，候选值依次为

因此 $D_2[7]=72$、$p_2[7]=4$。左侧终点 $2..6$ 只需保留切点上界 $4$；右侧终点 $8..12$ 只需保留下界 $4$。

下一步，左子问题中点 $j=4$ 扫描 $k=1,2,3$，费用为 $20,20,26$，取最左切点 $1$；右子问题中点 $j=10$ 扫描 $k=4,\dots ,9$，最优切点为 $5$，费用 $221$。继续递归，第二层得到

重复前缀和带来真实平局：$S_1=S_2=2$，所以在 $j=4$ 时切点 $1,2$ 同费。代码必须保留较小者，不能让循环顺序偶然决定输出。

单调性从哪里来 ​

非负 $w_i$ 使 $S$ 非降。候选矩阵 $M_{j,k}=D_{t-1}[k]+(S_j-S_k{)}^2$ 在四个有限可行格子上满足Monge 四点不等式公理库Monge 数组与交叉交换不等式Monge array · Monge matrix用任意四个有序格子的交换不等式控制行极小值的位置，并把平方分段费用转化成可证明的候选单调性。，因为其四点差为 $-2(S_{j^{\prime }}-S_j)(S_{k^{\prime }}-S_k)\le 0$。

若相邻两行最优切点逆序，设较早行选右列 $b$、较晚行选左列 $a<b$。两个切点在较早行都合法，且上层费用有限，于是上述四点不等式适用。上行最左规则使右列严格优于左列，Monge 性迫使下行仍严格偏好右列，矛盾。这直接证明了递归所需的单调性，也照顾了 $k<j$ 的阶梯边界。

负工作量给出的失败证书 ​

若改成 $w=(-1,-2,-2,2)$，前缀和为 $(0,-1,-3,-5,-3)$。第二层终点 $2,3,4$ 的最左切点是 $(1,2,1)$，发生倒退。正确费用为 $(5,13,5)$。

分治先求中点 $j=3$，得到切点 $2$，随后错误地要求 $j=4$ 只能从 $k\ge 2$ 转移，漏掉真正的切点 $1$，返回 $9$。错误不是浮点误差，也不是递归边界少一格，而是输入失去已证明的结构。允许任意查询顺序的Li Chao 树公理库Li Chao 直线树Li Chao tree · Li Chao segment tree把离散查询坐标递归二分，每个结点保留中点胜者，把另一条线送往唯一仍可能获胜的半边。仍可利用平方展开处理这一例。

固定递归深度时，各结点的候选区间有序相接，只有端点可能重叠，总扫描长度为 $O(n)$；递归深度 $O(\log n)$，故一层 $O(n\log (n+1))$，$K$ 层为 $O(Kn\log (n+1))$。只求值可用两行 $O(n)$ 存储与 $O(\log n)$ 栈；要一次性保存完整分段回溯表，则需 $O(Kn)$ 个切点。

若费用矩阵更强地满足全单调性公理库全单调矩阵与行极小值Totally monotone matrix把行极小列的单调性要求推广到所有保序子矩阵，用严格二乘二比较刻画可安全删行删列的结构。，且能随机访问表项，SMAWK公理库SMAWK 全单调矩阵搜索SMAWK algorithm交替执行列淘汰、奇数行递归与有界插值，在线性求值次数内找出全单调矩阵的每行最左极小值。可以进一步把每层求值降为线性。若费用展开成直线查询，单调直线下包络公理库单调直线下包络优化Monotone convex hull trick · Monotone line container把候选转移改写成直线，在斜率与查询点都单调时用双端队列维护下包络，并以交点顺序证明删线安全。也是另一条路。分治法的优点是直接使用最优切点次序，不要求每个费用都具有直线形式。

测试时应把每层每个值和最左切点都与朴素递推比较。只比最终最小费用可能漏掉中间切点错误，直到后续某次重建才暴露。随机含零负载、全零负载、$K=1$、$K=n$，以及故意破坏单调性的输入，各自检验不同的边界。