学习 monotone minima

[GoBigorGoHome]

monotone minima

minima 是名词 minimum 的复数形式。

monotone minima 说的是矩阵的一种性质。若一个矩阵的每一行的最小值（若有多个取最左边那一个）所在的列的编号从上到下是单调不降的，就说这个矩阵是 monotone 的。若一个矩阵的每个子矩阵都是 monotone 的，就说这个矩阵是 totally monotone 的。

子矩阵（英语：submatrix）是在矩阵选取部分行、列所组成的新矩阵。

试证明：
矩阵 $A$ 是 totally monotone 的 $\iff$ $A$ 的每个 2x2 子矩阵都是 monotone 的。

例题

坐标平面上有 $N$ 个房屋和 $M$ 个商店。第 $i$ 个房屋的坐标是 $(p_i, 0)$。第 $j$ 个商店的坐标是 $(x_j, y_j)$。满足

• $p_1 < p_2 < \dots < p_N$
• $x_1 \le x_2 \le \dots \le x_M$

考虑矩阵 $D_{N\times M}$， $D_{i,j}$ 是第 $i$ 个房屋到第 $j$ 个商店的距离。证明 $D$ 是 totally monotone 的。