参考
psj 的 apio 讲课，《决策单调性与四边形不等式》
p_b_p_b 的学习笔记。
csy 的讲课
oiwiki
一维的决策单调性
将 dp 抽象一下，给定一个向量 \(f\) 和一个矩阵 \(A\)，考虑求出一个向量 \(g_i=\min_j(f_j+a_{i,j})\)。
如果一个矩阵 \(A\) 的第 \(i\) 行的最小值的位置 \(b_i\) 是单调不减的就是单调矩阵。如果一个矩阵所有的子矩阵都是单调矩阵就称 \(A\) 是完全单调矩阵。
四边形不等式 \(i\le j,x\le y\)，\(A_{i,x}+A_{j,y}\le A_{i,y}+A_{j,x}\)。如果 \(j=i+1,y=x+1\) 满足四边形不等式，则 \(A\) 满足四变形不等式。满足四边形不等式的矩阵是蒙日矩阵。蒙日矩阵每一行或每一列加上一个常数 \(C\) 单调性不变。
由于蒙日矩阵一定是完全单调矩阵，所以dp方程有决策单调性
一般做法分治，假设当前分治区间是 \([l,r]\) 答案区间是 \([x,y]\) 考虑求出第 \(mid=\frac{l+r}{2}\) 行的最小值的位置 \(p\)，那么 \([l,mid-1]\) 的答案只能在 \([x,p]\) 取到，同理 \([mid+1,r]\) 的答案只能在 \([p,y]\) 取到，递归即可。
一般做法二分栈，对于任意两列，左边的列在一段前缀最优，右边的列在一段后缀更优。所以我们可以求出当前列第一个不如下一列的位置，这个二分求出。
NOI2009 诗人小G
直接列出转移方程 \(dp_i=length(j,i)^p+dp_j\)，这个幂函数显然是凸的于是它有决策单调性于是直接二分栈即可。
loj6039 雅礼集训2017 Day5 珠宝
把 \(C\) 相同的物品分成一组，肯定是从大到小选，记方程 \(f_{i,j}\) 代表前 \(i\) 组选则总体积为 \(j\) 个的最大收益，转移可以写成 \(f_{i,j}=\max f_{i-1,k}+s(i,\frac{j-k}{i})\)。其中 \(s({i,{j-k}{i})\) 是前缀和。
那这个 \(s({i,\frac{j-k}{i}})\) 是单调的所以显然有决策单调性，按照模 \(i\) 个余数分类，然后直接分治即可。
CTT2018 ZYB的游览计划
分治做法的优势，在于如果矩阵元素不能 \(O(1)\) 计算的时候，如果可以快速扩展，用分治法类似莫队算法加入删除复杂度不变。而这一题只需要维护集合内的点的dfs序的顺序即可。
CF868F Yet Another Minimization Problem
和上一题近乎一样的做法。
SMAWK 算法，一个 \(O(n)\) 的做法，好像除了卡交互次数没什么出出来卡科技的必要，而省选NOI也不大可能出这种交互题，所以咕咕咕。
Wilber 算法，解决了 SMAWK 不能在线的问题。
Eppstein 算法，解决交错转移的问题。
CF1423M Milutin's Plums
uoj672 UNR#5 航天飞机调度
可以去看我的洛谷博客
二维的决策单调性问题
形如 \(f_{i,j}=\min_k(f_{i,k}+f_{k+1,j})+w_{i,j}\) 这样的方程，如果 \(w_{i,j}\) 是蒙日阵且 \(w\) 满足区间单调性。
引理 \(f\) 满足四边形不等式。
这里先不证明。
定理 记 \(p_{i,j}=\mathrm{arcmin}_k(f_{i,k}+f_{k+1,j})\)，则 \(p_{i,j-1}\le p_{i,j}\le p_{i+1,j}\)。
这个对于每个 \(i\) 构造矩阵 \(a_{j,k}\) 即可，显然 \(a\) 是蒙日阵。
IOI2000 邮局
比较板子了吧...
蒙日矩阵乘法
一般的蒙日矩阵可以做到 \(O(n^2)\) 乘法。
蒙日矩阵对乘法封闭，即 \(A,B\) 是蒙日矩阵 \(C=AB\) 也是蒙日矩阵。
只需证明对 \(\forall i_1\le i_2,j_1\le j_2\)，都满足四边形不等式。假设 \(C_{i_1,j_2}\) 取到最小值的位置 \(k_1\)，\(C_{i_2,j_1}\) 取到最小值的位置为 \(k_2\)，则当 \(k_2\le k_1\) 时
当 \(k_1\le k_2\) 时同理。
本质上就是二维决策单调性。
lg8864 序列变换