四边形不等式优化
定义
假设有 $p_1\leqslant p_2\leqslant p_3\leqslant p_4.$
则 $c_{p_1,p_3}+c_{p_2,p_4}\leqslant c_{p_1,p_4}+c_{p_2,p_3}$ 被称为四边形不等式。
假设一个问题满足四边形不等式，那么它的决策点有单调性。
Proof:
假设有如下问题 ：现在有一个序列，我们要将其分割开来，分割一段 $[l,r]$ 的代价是 $c_{l,r}$，求最小代价。
设 $F_i$ 表示将前 $i$ 个位置分割完毕的最小代价，显然有暴力转移 ：
$$F_i=\min\limits_{j<i}\{F_j+c_{j,i}\}
$$
设 $F_i$ 的决策点为 $p_i.$ 假设存在 $x>y,p_x<p_y.$
根据最优决策的定义写出这个位置的转移式 :
$$F_x=F_{p_x}+c_{p_x,x}\leqslant F_{p_y}+c_{p_y, x}
$$
有 $p_x<p_y<y<x$，根据四边形不等式得到 :
$$c_{p_x,y}+c_{p_y,x}\leqslant c_{p_y,y}+c_{p_x,x}
$$
两不等式相加，得到 :
$$F_{p_x}+c_{p_x,y}\leqslant F_{p_y}+c_{p_y,y}
$$
与前文矛盾，故不存在 $x>y,p_x<p_y$，即满足决策单调性。
需要注意的是，只有最小化问题才能通过四边形不等式判定决策单调性。
区间形式
在实际做题中，我们经常遇到这样的 $\rm DP$ 方程 ：
$$f_{i,j}=\min\limits_{i\leqslant k<j}\{f_{i,k}+f_{k+1,j}+w_{i,j}\}
$$
我们考虑将四边形不等式推广到二维形式。
定理 $1$ ：若 $w$ 满足四边形不等式，并且对于任意 $a \leqslant b\leqslant c\leqslant d$，有 $w_{a,d}\geqslant w_{b,c}$，则 $f$ 也满足四边形不等式。
定理 $2$ ：设 $p_{i,j}$ 表示 $f_{i,j}$ 的决策点，若 $f$ 满足四边形不等式，则对于任意 $i<j$，有 $p_{i,j-1}\leqslant p_{i,j}\leqslant p_{i+1,j}.$
例题 ：$\rm [NOI1995] 石子合并$
转移技巧
有单峰性
这个性质结合决策单调性有均摊转移复杂度 $\Theta(1)$ 的做法 ：
记录一个指针表示当前的决策点，由于决策单调性所以它不会往回跳。进入每一层之后如果后面的决策点更优就跳到后面的决策点，根据单峰性这样一定不会漏掉解。
跳的次数是状态级别的，故转移均摊 $\Theta(1).$
仅有相邻层之间转移
这是一类特殊的二维 $\rm DP$，仅有相邻层之间的转移，没有同层之间的转移，同时满足决策单调性。
一般这种 $\rm DP$ 的时间复杂度是 $\Theta(n^3)$ 的，每次转移需要枚举前一层的所有点。
我们发现一个性质，在同一层中，先枚举哪一个是无关紧要的，因为同一层之间不会发生转移。
于是可以考虑分治，先转移 $mid$，得到其最优决策为 $p$，然后就可以将区间划分开，$[l,mid)$ 和 $(mid,r]$ 分别对应 $[tl,p]$ 和 $[p,tr].$
这样分治时间复杂度 $\Theta(n\log n).$
例题 ：$\rm [SDOI2016]征途$
贡献难算
首先有例题 ：存在一个长度为 $n$ 的序列，要将它划分成 $k$ 段，每段的价值被定义为不同的元素个数，要求最大化贡价值和。
数据范围：$n\leqslant 3.5\times 10^4,k\leqslant 50.$
首先有一个 $\Theta(n^3k)$ 的暴力 $\rm DP$，设 $dp_{i,j}$ 表示当分到 $i$ 时已经分了 $j$ 段的最大价值，有转移式 ：
$$dp_{i,j}=\max\limits_{k<i}\{dp_{k,j-1}+cnt_{k+1,i}\}
$$
其中 $cnt_{l,r}$ 表示从 $[l,r]$ 中不同颜色的个数，单次计算需要 $\Theta(n).$
我们发现只在相邻层之间发生转移，并且满足决策单调性（直观理解就是分得越多越容易亏），于是可以使用之前提到的分治法。
这样看起来是优化到 $\Theta(n^2k\log n)$，但我们考虑计算贡献的具体过程。我们每次只会计算 $dp_{mid}$ 的值，每次询问一个区间 $[i,mid]$ 的不同元素个数，可以考虑固定右端点移动左端点，容易发现移动次数是当前的分治区间长度，于是总移动次数不会超过 $n\log n$，故时间复杂度实际上为 $\Theta(nk\log n).$
例题：$\rm [P5574]任务分配问题$
常用算法
斜率优化
假设 $\rm DP$ 方程长成这种形式 ：
$$dp_i=\max\limits_{j<i}\{dp_j+(i)'+(i)(j)+(j)'+C\}
$$
即贡献为一个仅与 $i$ 有关的式子加上一个仅与 $j$ 有关的式子加上一个与两者都有关的乘积形式再加上一个常数，那么可以使用斜率优化。
我们发现 $dp_i,(i)',C$ 都与决策点的选择无关，于是可以把它们看作常数，将仅与 $j$ 有关的式子放在一边，可以得到方程 ：
$$dp_j+(j)'=-(i)(j)+dp_i-(i)'-C
$$
我们发现这是一次函数的形式，考虑构造平面，平面上有一些点，形如 $((j),dp_j+(j)').$ 我们发现，如果用一条斜率为 $-(i)$ 的直线经过某个点，那么截距为 $dp_i-(i)'-C.$ 由于我们要最大化 $dp_i$，等价于最大化这个截距，所以用这根斜率为 $-(i)$ 的直线从上到下平移，第一个碰到的点就是决策点。
于是现在问题就变成了维护一个凸包，我们发现有三种情况 ：
-
当加入点按照横坐标单调递增的顺序，并且询问点单调递增时，可以直接维护单调队列，加入点对比队尾斜率，取答案从队首即可。
-
当加入点按照横坐标单调的顺序时可以维护一个单调队列，每次加入时对比斜率，取答案二分。
-
当加入点无序时直接用平衡树 (std :: set) 维护，用 lower_bound 查找插入点，然后向左右两边依次弹出，取答案也使用 lower_bound。
例题 ：$\rm [SDOI2016]征途$
二分队列
若 $\rm DP$ 方程形如 ：
$$dp_i=\min\limits_{j<i}\{dp_j+w_{j+1,i}\}
$$
根据决策单调性的推论，任何两个点 $i,j(i<j)$ 之间都存在一个点 $k$，在 $k$ 之前一段转移点为 $i$，在 $k$ 之后某一段转移点为 $j.$
我们发现如果能快速计算 $w_{i,j}$，那么就能 $\Theta(\log n)$ 计算两个点 $i,j$ 之间的决策分界点。
我们发现所有相邻决策点的分界点可以用单调队列维护，具体来说 ：
这样就可以快速地维护相邻点的决策分界点了。
时间复杂度 $\Theta(n\log n).$
例题 ：$\rm [NOI2009]诗人小G$
二分栈
有些题可能会有这样的奇怪性质 ：每个决策点只会被自己前面的点反超。
我们发现某个决策点会经历这样的过程 ：一开始就比前面的优（否则就相当于一开始就被别人反超了），然后在最优决策的地方呆一会儿，最后被某个点反超。
严格来说这根本不算决策单调性，但是仍然可以用二分栈来维护，因为两点的优劣仍旧可以 $\Theta(\log n)$ 对比。具体来说 ：
- 加入一个点时，若其比堆顶劣，则直接扔掉，若其比堆顶优，则留下。
- 每一轮判断一下堆次顶是否比堆顶优，优则将堆顶弹出。
这样堆顶就一直是当前转移的决策点。
例题 ：$\rm [POI2011]Lightning~Conductor$
习题
[NOI1995] 石子合并
首先有暴力转移 ：
$$dp_{l,r}=\min\limits_{i\leqslant k<j}\{dp_{i,k}+dp_{k+1,j}+w_{i,j}\}
$$
记录前缀和 $sum$，这里 $w_{i,j}=sum_j-sum_{i-1}.$
$w$ 显然满足四边形不等式和包含单调，于是考虑四边形不等式优化。
然后就直接设 $p_{i,j}$ 表示 $dp_{i,j}$ 的转移点，成功转移的时候更新，枚举 $dp_{i,j}$ 断点的时候只需要枚举 $[p_{i,j-1},p_{i+1,j}]$ 即可。
时间复杂度 $\Theta(n^2).$
[SDOI2016]征途
首先易知，设每一天走的长度为 $d$，则答案为 ：
$$m\sum_{i=1}^m(d_i-ave)^2=m\sum_{i=1}^md_i^2-\left(\sum_{i=1}^md_i\right)^2
$$
容易观察到此题本质上是在求 $\left(\sum_{i=1}^md_i\right)^2_{\min}$，于是设 $f_{i,j}$ 表示当前已经考虑到第 $i$ 段，当前已经分成了 $j$ 段的最小 $\sum_{p=1}^jd_p.$ 枚举转移点，容易得到转移方程 ：
$$f_{i,j}=\min\limits_{k<i}\{f_{k,j-1}+(s_i-s_k)^2\}
$$
易证 $w_{i,j}=(s_j-s_i)^2$ 满足四边形不等式，所以该转移方程满足决策单调性。我们还发现转移方程只在相邻层之间转移，所以可以使用分治转移。
时间复杂度 $\Theta(n^2\log n).$
还有斜率优化的做法，注意到转移方程是可以变形的 ：
$$f_{i,j}=f_{k,j-1}+(s_i-s_k)^2
$$
$$\iff f_{i,j}=f_{k,j-1}+s_i^2-2s_is_k+s_k^2
$$
$$\iff f_{k,j-1}+s_k^2=2s_i\cdot s_k+f_{i,j}-s_i^2
$$
易知插入点横坐标有序，询问斜率也有序，所以可以直接使用单调队列维护，每一层分开转移。
时间复杂度 $\Theta(n^2).$
[P5574]任务分配问题
非常套路的分治 $+$ 决策单调性优化 $\rm DP.$
首先定义 $w_{i,j}$ 表示 $i\sim j$ 的顺序对个数，设 $f_{i,j}$ 表示当前已经考虑到第 $i$ 个任务，将他们分成 $j$ 段的最小顺序对数量之和，易得转移方程 ：
$$f_{i,j}=\min\limits_{k<i}\{f_{k,j-1}+w_{k+1,i}\}
$$
对于任意 $a\leqslant b\leqslant c\leqslant d$，使用容斥易证 $w_{a,c}+w_{b,d}-w_{b,c}\leqslant w_{a,d}$，故 $w$ 满足四边形不不等式。进一步的，$f$ 的转移满足决策单调性。
有了决策单调性，我们就可以分治转移，同时令人惊喜的是，转移时需要遍历一段连续的区间并计算每一个位置的贡献，于是用莫队和 $\rm BIT$ 维护一下就好了。
时间复杂度 $\Theta(nk\log^2n).$