“满足四边形不等式”是“满足决策单调性”的充分不必要条件，满足决策单调性的题目不一定可以使用这篇文章提到的优化方式。

解决的问题

对于转移方程为类似于下面情况的且 $n\le 2\times 10^5$，那么可以考虑用四边形不等式优化。

$f_{i}=\min\limits_{j=0}^i\{V(j,i)\}$

具体的 $V(j,i)$ 需要满足一些性质并且可以 $O(1)$ 求解。

考虑怎么最后 $f_i$ 实际上取到的 $j$ 就是 $f_i$ 的决策点，我们记其为 $p_i$。

四边形不等式

定义

如果 $\forall a,b,c,d\in[1,n]\cap \mathbb{Z}^+\wedge a\lt b\le c\lt d$ 满足 $V(a,d)+V(b,c)\ge V(a,c)+V(b,d)$，那么我们称 $V$ 满足四边形不等式。

这个结论看起来不好记，实际上也很难懂，可以简记为包含关系大于相交关系。

推论

如果 $\forall a,c\in[1,n]\cap\mathbb{Z}^+\wedge a\lt c$ 满足 $V(a,c+1)+V(a+1,c)\ge V(a,c)+V(a+1,c+1)$，那么也可以推出 $V$ 满足四边形不等式。

证明

令 $a'\gets a+1$ 得到：

$V(a+1,c+1)+V(a+2,c)\ge V(a+1,c)+V(a+2,c+1)$

把两式相加整理得到：

$V(a,c+1)+V(a+2,c)\ge V(a,c)+V(a+2,c+1)$

考虑一直重复上面的操作就可以把 $b=a+1$ 一直推广到 $b=+\infty$。

考虑通过类似的方法拓展 $c$，容易理解。

应用

四边形不等式的证明及其的麻烦，考试的是否可以直接通过暴力枚举 $a,c$ 来确定是否满足四边形不等式。

直接枚举 $2$ 个元素比去枚举 $4$ 个元素要优秀许多。

决策单调性

定义

如果 $\forall i,j\in[1,n]\cap\mathbb{Z}^+\wedge i\le j$ 满足 $p_i\le p_j$，那么我们称这个转移方程具有决策单调性。

定理

如果 $V$ 满足四边形不等式，那么这个转移方程满足决策单调性。

证明

设 $i,j\in[1,n]\cap\mathbb{Z}^+\wedge i\le j$，如果 $p_i\gt p_j$ 那么就有：

$f_i=V(p_i,i),f_{j}=V(p_j,j)$

根据定义有：

$V(p_i,i)+V(p_j,j)\ge V(p_i,j)+V(p_j,i)$

所以至少有一个 $f$ 是优于本来的，欲假设矛盾，因而得证。

决策单调性优化 DP

分治

如果 $V(j,i)$ 的计算与 $f_j$ 无关，那么可以考虑使用分治算法解决。

这样的转移方程很少，一般都是题目要求求出 $1$ 到 $n$ 之内所有的答案。

考虑设计函数 $\text{solve}(l,r,x,y)$ 表示求解 $[l,r]$ 的 $f$ 的值，而且其决策都是再 $[x,y]$ 中的。

计算 $f_{mid}$ 的值，假设其决策点再 $P$，那么显然对于 $[l,mid)$ 的 $f$ 的决策点都在 $[x,P]$，而对于 $(mid,r]$ 的决策点则是在 $[P,y]$ 里。

一直递归直到 $l=r$，时间复杂度为 $O(n\log n)$。

单调栈与队列

先假设所有的决策点都是 $0$，那么从前向后计算，尝试将在计算出 $f_i$ 之后将 $i$ 作为决策点。

因为其具有决策单调性，所以按照上面的方式进行更新，如果 $f_i$ 可以更新到 $f_x$，那么从 $f_x$ 到 $f_n$ 都是可以被 $f_i$ 更新的。

发现这个东西具有单调性，那么考虑去二分第一个满足用 $f_i$ 更新更有的节点。

在二分出第一个位置假设是 $p$，那么考虑把 $[p,n]$ 合并为一个区间，表示这个区间的决策点都是 $i$。

时间复杂度是 $O(n\log n)$，$\log$ 是二分。

因为一次操作最多只会新增一个区间，所以总共清除的区间数最大只有 $n$，就是 $O(n)$ 的。