动态规划相关
通常需要排除一些不可能的决策点或者排序，以满足最优子结构。这通常在常数优化时被 oier 考虑到。
四边形不等式
-
区间包含单调性：如果对于任意
，均有
成立，则称函数
关于区间包含关系具有单调性。
-
四边形不等式：如果对于任意
，均有
成立，则称函数
1D/1D的优化
我们常有方程
定理 若函数 满足四边形不等式，则
满足决策单调性，即：记
表示从
转移过来的状态
,
表示最优决策点，有
。
2D/1D的优化
区间类动态规划中，常常遇到形如下面的转移方程：
对于不同的问题， 的边界取值可能不同。这对我们讨论的问题没有影响（源于华中师大一附中赵爽）。考试时请打表。
定理 若函数 满足四边形不等式（且满足区间包含单调性？），则
也满足四边形不等式。（用数学归纳法证明）
定理 若 满足四边形不等式，则
满足决策单调性，即：记
表示最优决策点，则有
。
即若函数 满足四边形不等式，则
满足决策单调性。只需枚举决策
k in c[i][j-1] to c[i+1][j]
核心代码
for(int bias=1; bias<n; bias++) // bias=j-i, where[i,j]
{
for(int i=1,j; (j=i+k)<=n; i++)
{
f[i][j]=1e18;
for(k=c[i][j-1]; k<=c[i+1][j]; k++)
if(..<..) update f and c;
f[i][j]+=x[j]-x[i-1];
}
}
满足四边形不等式的函数类
摘自oi wiki。
为了更方便地证明一个函数满足四边形不等式，我们有以下几条性质：
性质 1. 若函数 均满足四边形不等式（或区间包含单调性），则对于任意
，函数
也满足四边形不等式（或区间包含单调性）。
性质 2. 若存在函数 使得
，则函数
满足四边形恒等式。当函数
单调增加时，函数
还满足区间包含单调性。
性质 3. 设 是一个凸函数，若函数
满足四边形恒等式并且对区间包含关系具有单调性，则复合函数
也满足四边形不等式。
性质 4. 设 是一个单调增加的凸函数，若函数
满足四边形不等式并且对区间包含关系具有单调性，则复合函数
也满足四边形不等式和区间包含单调性。
凸函数（Convex Function）的定义在国内教材中有分歧，本文指（可微的）下凸函数，即一阶导数单调增加的函数。
更高更妙的记忆与性质
若两函数 均满足四边形不等式（或区间包含单调性），则其（正系数）线性组合也满足四边形不等式（或区间包含单调性）。
若存在函数 使得
，则
满足四边形恒等式。当函数
单调增加时，函数
还满足区间包含单调性。
设 是一个凸函数，若函数
满足四边形恒等式并且对区间包含关系具有单调性，则其复合函数
也满足四边形不等式。若
还单调增加，复合函数
也满足区间包含单调性。
目前已经见过的式子
为凸函数
，其中
单调性互异：满足四边形不等式
