Quadrilateral_Inequality
说明：本篇中的一切决策点都是在整数意义下的，这样归纳法才能成立。
实际上我根本不会四边形不等式那一套理论。DP 的时候打个表，看看决策点是否是单调的，如果是，用就完了。
—— xpp
然后下面的东西基本就都不用学啦。
一、定义
若对于 $a\le b\le c\le d$，满足：
$$w(a,d)+w(b,c)\ge w(a,c)+w(b,d)$$
则称 $w$ 满足四边形不等式。（简记为“包含大于交叉”）
若对于任意整数 $a<b$，都有：
$$w(a,b+1)+w(a+1,b)\ge w(a,b)+w(a+1,b+1)$$
则称 $w$ 满足四边形不等式（亦称为凸完全单调性，因为此时 $w(x,i+1)-w(x,i)$ 单调不增）。
关于上面两种定义等价的证明：
对于 $a<c$，有 $w(a,c+1)+w(a+1,c)\ge w(a,c)+w(a+1,c+1)$。
对于 $a+1<c$，有 $w(a+1,c+1)+w(a+2,c)\ge w(a+1,c)+w(a+2,c+1)$。
两式相加，消去相同项，有 $w(a,c+1)+w(a+2,c)\ge w(a,c)+w(a+2,c+1)$。
依次类推，我们的 $a+1$ 可以扩展称所有大于 $a$ 小于 $c$ 的整数（包括 $b$，等于的时候不用证就略了）（扩展就是不断将 $a$ 替换为 $a+2$，$a+3$ 类似的）。
因此，对于任意 $a\le b\le c$，有 $w(a,c+1)+w(b,c)\ge w(a,c)+w(b,c+1)$。
同理，我们将上面的过程类似的做一遍（把 $a+1<c$ 的假设换成 $a<c+1$），又可以将 $c+1$ 扩展到 $d$。
因此，对任意 $a\le b\le c\le d$，有 $w(a,d)+w(b,c)\ge w(a,c)+w(b,d)$。
我们证明了一个方向的充分性，因为另一个方向的充分性实在太显然我就不证了。
二、1D1D DP
决策单调性：
对于形如 $f(i)=\min_{j=0}^{i-1} \{ f(j)+w(j,i) \}$ 的状态转移方程，记 $p(i)$ 为 $f(i)$ 取到最小值时的 $j$ 的值。此时称 $p(i)$ 为 $f(i)$ 的最优决策。
若 $p$ 在 $[1,n]$ 上单调不降，则称 $f$ 具有决策单调性。
决策单调性定理：
对于 $f(i)=\min_{j=0}^{i-1}{f(j)+w(j,i)}$，若函数 $w$ 满足四边形不等式，则 $f$ 具有决策单调性。
证明：设 $j<p(i)$，由 $p(i)$ 的最优性，易知：
$$f(p(i))+w(p(i),i)\le f(j)+w(j,i)$$
设 $i’>i$，因此我们有 $j<p(i)<i<i’$，根据四边形不等式：
$$w(j,i’)+w(p(i),i)\ge w(j,i)+w(p(i),i’)$$
移项有：
$$w(p(i),i’)-w(p(i),i)\le w(j,i’)-w(j,i)$$
与证明中的第一个不等式相加：
$$f(p(i))+w(p(i),i’)\le f(j)+w(j,i’)$$
翻译一下就是若 $j<p(i)$，则 $j$ 作为 $f(i’)$ 的决策一定不如 $p(i)$ 作为 $f(i’)$ 的决策优秀。
再换句话说，$p(i’)$ 一定大于等于 $p(i)$（因为不可能小于 $p(i)$，还能怎么样？）。
所以 $f$ 此时具有决策单调性。
上述定理的证明过程比较重要，记住思路，可以将决策单调性扩展到更多的转移。
比如说：$f(i)=\min_{j=0}^{i-1}{kf(j)+w(j,i)}$，这里 $k\in \mathbb{R}$，仿照上面的证明就能知道，它仍然具有决策单调性。
应用方法：栈，三元组，以及二分。。。
这里我很难一下解释清楚这个做法，大概说明一下：
- 新加入一个决策点 $i$
- 寻找上一个最优决策点 $j$ 最左能到达哪里（不妨设为 $l$）。
- 如果说 $l$ 由 $i$ 决策时比 $j$ 时优，那么显然 $j$ 能决策的点（就是 $[l,n]$）都要换成 $i$ 为决策点了。
- 接下来显然还可以以此类推找到上上个决策点，上上上个决策点，直到存在一个 $l$ 的最优决策不再是 $i$。
- 找到这种决策点的时候我们就要在 $j$ 所决策的区域上二分，看我们最多能决策哪一段区间。
- 借助三元组和栈来完成这个过程的模拟。
- 时间复杂度 $O(n\log n)$。
当然在一些特殊的情况我们还有特殊分治的做法（当然这个方法还可以沿用），更加方便：P3515。
三、2D1D DP
注意：取 $\max$ 时下面的东西都不能用。。。但一般这个时候能用贪心解决所以不要太担心。。。
区间包含单调性：
对于任意 $a\le b\le c\le d$，都有 $w(a,d)\ge w(b,c)$，则称 $w$ 满足区间包含单调性。
定理：
对于 $f(i,j)=\min_{k=i}^{j-1}\{f(i,k)+f(k+1,j)\}+w(i,j)$（满足 $f(i,i)=w(i,i)=0$），若 $w$ 满足：
- 四边形不等式
- 区间包含单调性
则 $f$ 满足四边形不等式。
证明：显然有 $f(i,i+1)=w(i,i+1)$。
下面考虑归纳法证明。
当 $j-i=1$ 时，即 $i+1=j$ 时，显然：
$$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)$ 的最优决策是 $i+1$，则：
$$\begin{aligned}
f(i,i+2) & =f(i,i+1)+f(i+2,i+2)+w(i,i+2)
\\
& =w(i,i+1)+w(i,i+2)
\\
& \ge w(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)\end{aligned}$$上面的不等式证明部分使用了 $w$ 的包含单调性。
若 $f(i,i+2)$ 的最优决策点是 $i$，则：
$$\begin{aligned}
f(i,i+2)&=f(i,i)+f(i+1,i+2)+w(i,i+2)
\\
&= w(i+1,i+2)+w(i,i+2)
\\
&\ge w(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)
\end{aligned}$$上面的不等式部分证明仍然是包含单调性。
上面两种情况的不等式即 $f(i,i+2)\ge f(i+1,j+1)+f(i,j)$，将 $f(i,i+2)$ 替换为 $f(i,j+1)+f(i+1,j)$，我们就得到了四边形不等式的形式。
因此，当 $j-i=1$ 时，四边形性不等式对 $f(i,j)$ 成立。
使用数学归纳法，设 $j-i<k$ 时，四边形不等式对 $f(i,j)$ 成立，考虑 $j-i=k$ 的情况。
设 $f(i,j+1)$ 以 $x$ 为最优决策点，$f(i+1,j)$ 以 $y$ 为最优决策点，不妨设 $i+1\le x\le y<j$。
根据 $x$，$y$ 的最优性：
$$\begin{aligned}
& f(i,j+1)+f(i+1,j)
\\
=&f(i,x)+f(x+1,j+1)+w(i,j+1)
\\
& +f(i+1,y)+f(y+1,j)+w(i+1,j)
\end{aligned}$$对于 $f(i,j)$ 和 $f(i+1,j+1)$，$x$ 和 $y$ 是任意决策（不一定最优），因此有：
$$\begin{aligned}
& f(i,j)+f(i+1,j+1)
\\
\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)
\end{aligned}$$因为 $w$ 满足四边形不等式：
$$w(i,j+1)+w(i+1,j)\ge w(i,j)+w(i+1,j+1)$$
根据归纳假设：
$$f(x+1,j+1)+f(y+1,j)\ge f(x+1,j)+f(y+1,j+1)$$
结合上面的几个式子（懒了，就是代换一下），我们就得到：
$$\begin{matrix}f(i,j+1)+f(i+1,j)\ge f(i,j)+f(i+1,j+1)&\square \end{matrix}$$
二维决策单调性定理：
在状态转移方程 $f(i,j)=\min_{k=i}^{j-1}\{f(i,k)+f(k+1,j)\}+w(i,j)$（满足 $f(i,i)=w(i,i)=0$），记 $p(i,j)$ 为 $f(i,j)$ 取到最小值的时候 $k$ 的值，称 $p(i,j)$ 为 $f(i,j)$ 的最优决策点。
若 $f$ 满足四边形不等式，那么对于任意 $i<j$，有 $p(i,j-1)\le p(i,j)\le p(i+1,j)$。
证明：记 $p’=p(i,j)$，对于任意 $i<i+1\le k\le p’$ 因为 $f$ 满足四边形不等式：
$$f(i,p’)+f(i+1,k)\ge f(i,k)+f(i+1,p’)$$
移项：
$$f(i+1,k)-f(i+1,p’)\ge f(i,k)-f(i,p’)$$
根据 $p’$ 的最优性：
$$f(i,k)+f(k+1,j)\ge f(i,p’)+f(p’+1,j)$$
因此：
$$\begin{aligned}
& [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(i,p’)]+[f(k+1,j)-f(p’+1,j)]
\\
=& [f(i,k)+f(k+1,j)]-[f(i,p’)+f(p’+1,j)]
\\
\ge & 0
\end{aligned}$$这意味着对于 $f(i+1,j)$，$p’$ 比任意的 $k\le p’$ 要优。因此 $p(i+1,k)\ge p(i,j)$。
类似地，我们也可以证明 $p(i,j-1)\le p(i,j)$。
四、一些性质
复读 OI wiki，但是把我觉得不太靠谱的给删了。。。
主要是帮助推导四边形不等式的。。。
若 $w_1$，$w_2$ 均满足四边形不等式，则对于任意 $c_1$，$c_2$，都有 $c_1w_1+c_2w_2$ 满足四边形不等式。
证明：显然（把两个四边形不等式分别乘上 $c_1$，$c_2$ 并相加就能得到该结论）。。。
若存在函数 $f$，$g$ 使得 $w(l,r)=f(r)-g(l)$，则函数 $w$ 满足四边形恒等式。若 $f$，$g$ 单调递增，则 $w$ 满足区间包含单调性。
证明：显然（用定义）。。。
设 $h(x)$ 是一个单调增加的函数，若函数 $w$ 满足四边形不等式和区间包含单调性，则 $h(w(l,r))$ 也满足四边形不等式和区间包含单调性。
证明：
对于区间包含单调性：
设 $l\le l’\le r’\le r$，显然 $w(l’,r’)\le w(l,r)$，又 $h$ 是增函数，就有 $h(w(l’,r’))\le h(w(l,r))$。
对于四边形不等式：
任取 $a\le b\le c\le d$，根据 $w$ 满足四边形不等式：
$$w(a,d)+w(b,c)\ge w(a,c)+w(b,d)$$
移项，并根据区间包含单调性：
$$w(a,d)-w(b,d)\ge w(a,c)-w(b,c)\ge 0$$
记 $t=w(a,d)-w(b,d)\ge 0$，则上式等价于：
$$
w(a,c)\le w(b,c)+t
\\
w(a,d)=w(b,d)+t
$$根据 $h$ 的单调性：
$$
h(w(a,c))-h(w(b,c))\le h(w(b,c)+t)-h(w(b,c))
$$$$
h(w(a,d))-h(w(b,d))=h(w(b,d)+t)-h(w(b,d))
$$设 $\Delta h(x)=h(x+t)-h(x)$，由单调性，得到：
$$\begin{aligned}
h(w(a,c))-h(w(b,c)) & \le \Delta h(w(b,c))
\\
& \le \Delta h(w(b,d))
\\
&=h(w(a,d))-h(w(b,d))
\end{aligned}$$即四边形不等式的形式。