Monge 数组与交叉交换不等式

把两行看成两个有序位置，把两列看成两个有序候选。Monge 条件说：把较早位置配给较早候选、较晚位置配给较晚候选，总成本不高于交叉配对。它不是逐格递增条件，而是一种交换两项以后不吃亏的关系。

也可以把不等式改写为

向下移动行号时，左列相对右列的成本差不会减小。因此右列一旦严格击败左列，在更低的行仍会严格击败它；右列不会赢了一次又把优势交回左列。

要证明最左极小列单调，反设上行选 $\ell$、下行选 $j<\ell$。上行因为选的是最左极小值，有 $A_{ij}>A_{i\ell }$；差值不等式推出 $A_{kj}>A_{k\ell }$，与下行选 $j$ 矛盾。证明只用一个 $2\times 2$ 子矩形，却排除了所有逆序决策。

平方距离为何具有 Monge 性 ​

取递增坐标 $x=(0,2,5)$、$y=(-1,1,4,6)$，定义 $A_{ij}=(x_i-y_j{)}^2$，得到

按从零开始的列号，最左极小列为 $(0,1,2)$。在前两行、前两列中，顺序配对成本 $1+1=2$，交叉配对成本 $1+9=10$。一般地，展开平方后四个纯平方项互相消去：

条件来自两组坐标的同向排序，允许相邻坐标相等。若把最后一行第一项改成 $-10$，极小列就变成 $(0,1,0)$。中间行与末行、前两列形成的四点和为 $9+16=25$，而交叉和为 $1-10=-9$，Monge 条件确实被破坏。这不是只凭画出的极小值趋势判断结构，而是能定位到违反条件的四个格子。

只检查相邻小方块是否足够 ​

对于完整有限实值矩阵，只需检查每个相邻 $2\times 2$ 方块。

令

任意大矩形的四点差恰等于 $\sum _{r=i}^{k-1}\sum _{s=j}^{\ell -1}{\delta }_{r,s}$，内部项全部望远镜相消。因此相邻差都非正就推出全部四点不等式，核验时间为 $O(mn)$。这有助于检查一张显式表，但不会使读入整表本身少于 $mn$ 个元素。

行、列各加任意常数仍保留 Monge 性，因为四点差中的偏置也抵消。把行列任意打乱则一般不保留；顺序是定义的一部分。含 $+\mathrm{\infty }$ 的缺项表还涉及无穷差与可行域形状，不能直接照搬相邻差的实数消去论证。

分段递推中的四点差 ​

将非负工作量 $w_1,\dots ,w_n$ 分成连续批次，记前缀和 $S_j=\sum _{q\le j}{w}_q$，一个批次 $(k,j]$ 的费用为 $(S_j-S_k{)}^2$。固定动态规划公理库动态规划Dynamic programming在有限或良基的状态依赖上复用已计算结果的算法设计范式。上一层 $D_{t-1}$，当前层的候选矩阵是

在四个候选都可行、上一层费用有限时，列偏置 $D_{t-1}[k]$ 抵消，四点差成为

其中 $j<j^{\prime }$、$k<k^{\prime }$。这就给出最优切点单调的来源。非负工作量不是装饰：它让前缀和保持顺序，负数可能破坏四点差的符号。

Monge 性还会在任意保序删行、删列后保留，所以它推出全单调性公理库全单调矩阵与行极小值Totally monotone matrix把行极小列的单调性要求推广到所有保序子矩阵，用严格二乘二比较刻画可安全删行删列的结构。。SMAWK公理库SMAWK 全单调矩阵搜索SMAWK algorithm交替执行列淘汰、奇数行递归与有界插值，在线性求值次数内找出全单调矩阵的每行最左极小值。利用后者在线性数量的求值中找出所有行极小值；分治 DP 优化公理库决策单调的分治 DP 优化Divide-and-conquer DP optimization在已证明最优切点单调的分层递推中，先求中间状态，再用它收紧左右候选区间，逐层安全省去转移。只需更弱的当前行决策单调性。选择算法前，应先说明表项怎样 $O(1)$ 求值，以及非法候选怎样处理，而不是只贴上“Monge”标签。

本页的 Monge 是离散成本数组的结构；Monge 输运问题公理库Monge 输运问题Monge transport problem用确定映射搬运概率质量，先检查推前约束是否可行，再讨论最小成本。中的同名人物则出现在把质量由一个空间搬到另一个空间的映射优化模型里。二者可以在有序离散运输中相遇，但数组不等式本身不定义一个输运映射。