决策单调性
四边形不等式
定义
若对于 \(\forall i\le j\le k \le l\)，有 \(W_{i,k}+W_{j,l}\le W_{i,l}+W_{j,k}\)，则称 \(W\) 满足四边形不等式。
性质 & 判定
对于 \(\forall i\lt j\)，有 \(i\lt i+1\le j\lt j+1\)，于是 \(W_{i,j}+W_{i+1,j+1}\le W_{i,j+1}+W_{i+1,j}\)，这是显然的。
那么通过这个，能否逆推出 \(W\) 满足四边形不等式呢？答案是可以的。
考虑使用数学归纳法：
现假设对于 \(k\in\mathbb{Z_+},i\le i+k\lt j\le j+1\)，满足
\[W_{i,j}+W_{i+k,j+1}\le W_{i,j+1}+W_{i+k,j} \tag{1} \]只需证明
\[W_{i,j}+W_{i+k+1,j+1}\le W_{i,j+1}+W_{i+k+1,j} \tag{∗} \]由假设知 \(i+k\le i+k+1\le j\le j+1\)，于是
\[W_{i+k,j}+W_{i+k+1,j+1}\le W_{i+k,j+1}+W_{i+k+1,j} \tag{2} \]\((1)+(2)\) 得到 \(W_{i,j}+W_{i+k,j+1}+W_{i+k,j}+W_{i+k+1,j+1}\le W_{i,j+1}+W_{i+k,j}+W_{i+k,j+1}+W_{i+k+1,j}\)
化简得 \(W_{i,j}+W_{i+k+1,j+1}\le W_{i,j+1}+W_{i+k+1,j}\)
又因为 \(k=1\) 时成立，故 \(\forall k,i+k\le j\) 有 \(W_{i,j}+W_{i+k+1,j+1}\le W_{i,j+1}+W_{i+k+1,j}\)
根据对称性，第二维上也满足这一性质，所以四边形不等式成立。
因此，四边形不等式的性质与定义互为充要条件，因为只涉及两个未知量且形式简单，所以在证明时通常就使用性质来证明。
决策单调性
一维 \(dp\)
对于有一类 \(dp\) 问题，其状态转移方程会满足这样的形式：\(f_i=\min\limits_{1\le j \lt i}\{f_j+V_{j,i}\}\)，在不作任何优化的情况下，复杂度为 \(\Omicron(n^2)\)。
其中，若 \(V\) 满足四边形不等式，则 \(f\) 的最优决策点具有单调性（单调不降）。
假设有 \(i\lt i'\)，下证 \(p_i\le p_{i'}\)
若 \(i\) 的最优决策点为 \(p_i\) 则一定有 \(\forall j\le p_i,f_j+V_{j,i}\ge f_i=f_{p_i}+V_{p_i,i}\)
因为 \(j\le p_i\lt i\lt i'\)，由四边形不等式得 \(V_{j,i'}-V_{j,i}\ge V_{p_i,i'}-V_{p_i,i}\)
两式相加得 \(f_j+V_{j,i'}\ge f_{p_i}+V_{p_i,i'}\)
这说明，对于 \(\forall i'\lt i\)，若 \(j\lt p_i\)，则 \(j\) 一定不优，即 \(p_{i'}\ge p_i\)，那么决策就具有单调不降性。
证毕。
那么我们就可以通过二分，将这个 \(dp\) 优化到 \(\Omicron(n\log n)\) 的复杂度。
二维 \(dp\)
有另一类 \(dp\) 问题，如果满足以下四个条件：
- \(f_{i,j}=\min\limits_{i\le k\lt j}\{f_{i,k}+f_{k+1,j}+W_{i,j}\}\)
- \(\forall i,f_{i,i}=W_{i,i}=0\)
- \(W\) 满足四边形不等式
- \(\forall a\le b\le c\le d,W_{a,d}\ge W_{b,c}\)
那么可以证明 \(f\) 也满足四边形不等式。
先从简单的情况开始证明，若 \(j=i+1\)，则有 \(i\lt i+1\le j\lt j+1\)，下证 \(f_{i,j+1}+f_{i+1,j}\ge f_{i,j}+f_{i+1,j+1}\)
将左式展开得到 \(f_{i,j+1}+f_{i+1,j}=f_{i,i+2}+f_{i+1,i+1}=f_{i,i+2}\)
对于 \(f_{i,i+2}\)，决策 \(k\) 的取值只有 \(i/i+1\) 两种情况，分类讨论之。
\(k=i\) 时：\(LHS=f_{i,i+2}=f_{i,i}+f_{i+1,i+2}+W_{i,i+2}\ge f_{i+1,i+2}+W_{i,i+1}=f_{i+1,i+2}+f_{i,i+1}=f_{i+1,j+1}+f_{i,j}=RHS\)
\(k=i+1\) 时：\(LHS=f_{i,i+2}=f_{i,i+1}+f_{i+2,i+2}+W_{i,i+2}\ge f_{i,i+1}+W_{i+1,i+2}=f_{i,i+1}+f_{i+1,i+2}=f_{i,j}+f_{i+1,j+1}=RHS\)
综上所述，当 \(j=i+1\) 时，\(f\) 满足判定式，即满足四边形不等式。
接下来考虑运用串值归纳法进行推广，若 \(j-i\lt k\) 时均满足，下证 \(j-i=k\) 时仍然满足。
假设 \(f_{i,j+1}/f_{i+1,j}\) 的最优决策点分别为 \(x/y\)，下面分两种情况讨论。
\(i\le x \le y \lt j\) 时，\(x+1\le y+1\le j\lt j+1 \rightarrow j-(x+1)\lt k\)，于是有：
\[\begin{align} LHS &= f_{i,x}+f_{x+1,j+1}+W_{i,j+1}+f_{i+1,y}+f_{y+1,j}+W_{i+1,j} \\ RHS &\le f_{i,x}+f_{x+1,j}+W_{i,j}+f_{i+1,y}+f_{y+1,j+1}+W_{i+1,j+1} \\ i\lt i+&1\le j\lt j+1\rightarrow W_{i,j}+W_{i+1,j+1}\le W_{i,j+1}+W_{i+1,j} \tag{1}\\ j-(&x+1)\lt k \rightarrow f_{x+1,j}+f_{y+1,j+1}\le f_{x+1,j+1}+f_{y+1,j}\tag{2}\\ \end{align} \]\((1)+(2)\) 即得证。
\(i+1\le y\le x\le j\) 时，\(i\lt i+1\le y\lt j\rightarrow y-i\lt k\)，接下来与上面同理就可以证明。
于是对于 \(\forall i\lt j\)，都有 \(f_{i,j+1}+f_{i+1,j}\ge f_{i,j}+f_{i+1,j+1}\)，所以四边形不等式成立，证毕。
拥有了四边形不等式，下面来证明这样的 \(dp\) 转移时具有决策单调性，形式上：\(\forall i,j\)，有 \(p_{i,j-1}\le p_{i,j}\le p_{i+1,j}\)
为方便表示，下令 \(p=p_{i,j}\)
对于 \(\forall k,i\lt i+1 \le k \le p\)，有四边形不等式变形得 \(f_{i+1,k}-f_{i+1,p}\ge f_{i,k}-f_{i,p}\)
决策作差得到：
\[\begin{align} &\ \ \ \ \ (f_{i+1,k}+f_{k+1,j}+W_{i+1,j})-(f_{i+1,p}+f_{p+1,j}+W_{i+1,j}) \\ &=(f_{i+1,k}-f_{i+1,p})+f_{k+1,j}-f_{p+1,j} \\ &\ge (f_{i,k}+f_{k+1,j})-(f_{i,p}+f_{p+1,j}) \\ &\ge 0 \end{align} \]于是得到了 \(\forall i' \gt i\)，若 \(p_{i',j}\lt p_{i,j}\) 则一定不优， 所以 \(p_{i',j}\ge p_{i,j}\)。同理可证 \(\forall j' \gt j\)，有 \(p_{i,j'}\ge p_{i,j}\)，所以 \(p_{i',j'}\ge p_{i,j}\)，证毕。
复杂度分析
转移到 \((i,j)\) 时，只枚举 \([p_{i,j-1},p_{i+1,j}]\) 这一区间即可，复杂度为 \(\Omicron(n^2)\)
考虑如下这样一个网格图
只有红线之上的格子会被转移到，对每个格子计算贡献，若右边有格子，则被减一次；若上边有格子，则被加一次。于是 \(n\) 条对角线，每条对角线贡献的最大复杂度为 \(\Omicron(n)\)，总复杂度为 \(\Omicron(n^2)\)，且状态数也为 \(O(n^2)\)，于是最后复杂度即为 \(\Omicron(n^2)\)。
如上所示，证明超级繁琐，赛时完全不可证明，于是其实如果发现 \(dp\) 非常简单，而且已经没有向其他方向优化的空间了，那么就猜一猜有决策单调性，把决策打表出来看看有没有单调性就好了，至于上面的证明和结论其实没啥用喵。
分治决策单调性
在通常一维 \(dp\) 的情况下，一段区间的贡献是好算的。但是如果不好算呢？例如：数字种类数，顺序对个数。这些问题如果能够莫队的话会感觉简单很多。那么我们其实可以采取类似的方案，类似于整体二分地分治地去做，递归区间 \([l,r]\) 的最优决策点在区间 \([L,R]\) 中，每次找到 \([l,r]\) 的中点，找到中点的最优决策点 \(p\)，然后将 \([L,R]\) 分为 \([L,p]\) 和 \([p,R]\) 去做，这样我们会有 \(\Omicron(\log n)\) 层，每一层递归是 \(\Omicron(n)\) 的，维护区间与莫队同理，不难发现这个复杂度大概也是 \(\Omicron(n\log n)\) 级别的。
void solve(int l, int r, int L, int R, int k){
int mid = (l + r) >> 1, p = 0;
for(int i = min(R, mid - 1); i >= L; --i){
split(i + 1, mid); // 移动到当前区间
if(f[i][k - 1] + now <= f[mid][k]) f[mid][k] = f[i][k - 1] + now, p = i; // 记录最优决策点
}
if(l < mid) solve(l, mid - 1, L, p, k);
if(r > mid) solve(mid + 1, r, p, R, k);
return;
}