0. 前言
你打开了一道题，你发现是个 DP，你写出了转移方程 f_i = \min \limits_{0 \leq j < i} \{f_j + v_{j,i} \}，你发现 v_{j,i} 可以 O(1) 计算。你兴致勃勃地写出了代码，却得到了满面 TLE。一看数据范围，n \leq 2 \times 10^5。
你点开题解，发现一种神奇的对于 v 的特殊性质进行优化的方法。这就是四边形不等式优化 DP。
1. 定义和性质
如果对于二维序列 w 中任意四个整数 a \leq b \leq c \leq d 都有 w_{a,d} + w_{b, c} \geq w_{a, c} + w_{b, d}，则称 w 满足足四边形不等式关系。
性质
若对于任意两个整数 i < i + 1 \leq j < j + 1，都有 w_{i, j + 1} + w_{i + 1, j} \geq w_{i, j} + w_{i + 1, j+1}，那么 w 满足四边形不等式。
证明：
取 i + 1 < i + 2 \leq j < j + 1，那么由上文的前提可得，我们令 i^{'} = i + 1，则有 w_{{i^{'}},j+1} + w_{{i^{'}+1},j} \geq w_{{i^{'},j}} + w_{{i^{'}+1,j+1}}，即 w_{i+1, j + 1} + w_{i + 2, j} \geq w_{i + 1, j} + w_{i + 2, j + 1}。
两不等式相加，即 w_{i,j+1} + w_{i + 1, j} + w_{i+1,j+1} + w_{i+2, j} \geq w_{i,j}+w_{i+1,j+1}+w_{i+1,j}+w_{i+2,j+1}，整理可得 w_{i, j+1} + w_{i + 2, j} \geq w_{i, j} + w_{i + 2, j + 1}。
接着取 i+2<i+3 \leq j < j + 1，可继续按照上面的做法推广，最终可得 w_{i, j + 1} + w_{i + 3, j} \geq w_{i, j} + w_{i + 3, j + 1}。
可以发现我们可以取 i+3<i+4 \leq j < j + 1 等等，都可以证出类似的结论。即对于任意 a \leq b \leq c < c + 1，都有 w_{a, c+1} + w_{b, c} \geq w_{a, c} + w_{b, c + 1}。接着我们只需要把 c 按照类似的方法推广到 d 即可。
取 a \leq b \leq c + 1 < c + 2，则有 w_{a, c+2} + w_{b, c+1} \geq w_{a, c+1} + w_{b, c + 2}。
两不等式相加，即 w_{a, c+1} + w_{b, c} + w_{a, c+2} + w_{b, c+1} \geq w_{a, c} + w_{b, c + 1} + w_{a, c+1} + w_{b, c + 2}，整理可得 w_{b, c} + w_{a, c+2} \geq w_{a, c} + w_{b, c + 2}。
取 a \leq b \leq c + 2 < c + 3，继续按照类似方法，有 w_{b, c} + w_{a, c + 3} \geq w_{a, c} + w_{b, c + 3}。
可无限取 c，即对于任意 a \leq b \leq c \leq d，都有 w_{a, d} + w_{b, c} \geq w_{a, c} + w_{b, d}。
至此，我们得以证明。
上述的结论通常用于证明 v 满足四边形不等式，与下文的 DP 优化关联不大。
PS：为什么叫四边形不等式？
对于任意四边形，显然有对角线的和 \geq 两对边之和，如图，AD+BC \geq AC+BD。证明方式为三角形两边之和大于第三边。
2. 优化 DP
考虑一类决策性 DP，其转移方程形如 f_i = \min \limits _{0 \leq j < i} \{f_j + v_{j, i}\}。这类转移方程通常是类似这样的题目：n 个数，要分成若干连续段，定义每一段的价值，要求最小化每段价值之和。这时我们设 f_i 表示前 i 个数分段的最小价值和，那么枚举 j 即枚举 i 属于哪一段，v_{j,i} 则是这一段的价值。
首先要引入什么是决策，我们设 p_i 表示表示对于 i 而言，我们枚举的 0 \leq j < i 中，使得 f_j + v_{j,i} 取到最值（在上文的转移方程中即最小值）的 j，则我们称 p_i 为 i 的决策点。
对于这一类问题，显然有朴素的 O(n^2) 计算方式。对于部分题目，如果 v 满足四边形不等式性质，我们可以考虑用下文的方式优化。
性质 1
若 v 满足四边形不等式，则 i 的决策点具有单调性。
性质 2
若有 x < j 使得对于某个 i > j，选取 j 的转移比 x 要优，则对于 i^\prime > i，取 j 也比 x 优。容易发现 j 为 i 的决策点时与性质 1 等价，即性质 1 是性质 2 的特殊情况。
特别注意需要满足 x<j。
证明：
由于 j 比 x 对 i 的贡献更优，所以有：f_j + v_{j, i} \leq f_x + v_{x, i}。因为 v 满足四边形不等式关系，则有 v_{x, i^\prime} + v_{j, i} \geq v_{x, i} + v_{j, i^\prime}，移项变为 v_{j, i^\prime} - v_{j, i} \leq v_{x, i^\prime} - v_{x, i}。
将最后一个不等式和第一个不等式相加，有 f_j + v_{j, i^\prime} \leq f_x + v_{x, i^\prime}。
证毕。
如何优化 DP
我们可以设初始时每个 i 的决策点都为 0，然后从前往后，依次用决策点算出 f_i 并尝试用 i 作为新的决策点更改其他点。
由于性质 2 成立，所以如果 f_i 可以更新 f_x，那么一定可以更新 f_{x+1} 到 f_n。所以 f_i 能更新的点一定是末尾一段。假设能更新的是 p \sim n，我们的目标就是找到 p。容易发现是可以二分的。
我们考虑维护一个队列，每个点维护三个数 l,r,c，表示 l \sim r 每个点的当前最优决策都为 c。这个队列是对于 c 的单调队列。我们对于 i，先从后往前找到 p 所在的 l,r,c，然后在 [l,r] 中二分 p 的位置并更新队列即可。
当然也有一些其他实现方法，例如分治维护，复杂度也是 O(n \log n)。
特别注意：
上文的做法对于四边形不等式是正确的，但对于普通的决策单调性是错误的。
对于普通的决策单调性 DP，只能保证最终的决策点是单调的，换句话说，只能保证性质 1 成立而不能保证性质 2 成立。
我们在维护单调队列进行更新的部分时，不能保证能找到 p。f_i 能更新的不一定是末尾一段。
我们可以通过几张图来更好地理解（下文的图中，横轴表示 j，纵轴表示 f_j + v_{j,i}）。
这张图给出的是 i=5 的一个例子。
假如我们只证明了决策单调性，那么对于 i=6，图可能是这样：
容易发现决策点也是不递减的，但是对于 i=5，1 比 0 优，但是对于 i=6，0 却比 1 优。
这在证明 v 满足四边形不等时式后是不成立的，因为其不满足性质 2。如果证明后，那么图可能是这样的：
容易看出，对于 j=0 \sim 4 的图，纵轴的点的相对关系是不变的。
所以可以看出，四边形不等式得到的结论强于决策单调性的。
注意，四边形不等式是证明 p 单调性的一种充分不必要方式。即证明 v 满足四边形不等式可以推出 p 单调，但 p 单调不一定要求 v 满足四边形不等式。
例题
P3195 [HNOI2008]玩具装箱
考虑一个 O(n^2) 的 dp。
设 f_i 表示前 i 个玩具的最小总费用，s_i 表示前 i 个玩具的长度和，即前缀和。
有转移方程：f_i = \min \limits_{0 \leq j < i} \{f_j + (s_i-s_j+i-j-1-l)^2\}。在这题中前文的 v 即后面的 (s_i-s_j+i-j-1-l)^2，我们只需要证明 v 满足四边形不等式即可。
至于如何证明，通常可以考虑在本地 O(n^4) 枚举 a, b, c,d，观察对于小数据是否满足，比较严谨的数学证明暂时略去。这里严谨的证明方式需要使用到文章开头的性质。
因为满足四边形不等式，把上述的优化 DP 方案加以修改即可。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
#define int long long
const int N = 5e4 + 5;
int a[N], n, l, dp[N], sum[N], op[N];
struct Node
{
int c, l, r;
}q[N];
inline int val(int i, int j) // 计算对于 j 而言，决策为 i 的答案
{
int s = sum[j] - sum[i] + j - i - 1 - l;
return dp[i] + s * s; // 即上文的 dp[i] + v
}
int hh, tt;
void insert(int x) // 用 x 更新决策方案
{
int pos = n + 1; // 临界点
while (hh <= tt && val(q[tt].c, q[tt].l) >= val(x, q[tt].l)) pos = q[tt--].l; // 找到用 x 作为决策点能更新到的队列，因为满足四边形不等式，所以更新的肯定是队列末尾的连续一段
if (hh <= tt && val(q[tt].c, q[tt].r) >= val(x, q[tt].r)) // 如果我们找到了这个区间
{
int l = q[tt].l, r = q[tt].r;
while (l + 1 < r) // 二分 l 到 r 中哪个点是临界点
{
int mid = l + r >> 1;
if (val(x, mid) <= val(q[tt].c, mid)) r = mid;
else l = mid;
}
q[tt].r = r - 1; // 更新队列和 pos
pos = r;
}
if (pos != n + 1) q[++tt] = { x, pos, n }; // 如果可以更新，就在后面更新
}
signed main()
{
scanf("%lld%lld", &n, &l);
for (int i = 1; i <= n; i++)
{
scanf("%lld", &a[i]);
sum[i] = sum[i - 1] + a[i];
}
hh = tt = 0;
q[0] = { 0, 1, n }; // 初始化，1 到 n 一开始的最优决策都是 0
for (int i = 1; i <= n; i++)
{
dp[i] = val(q[hh].c, i); // 计算已经求出最优决策点对于现在点的 dp 值
op[i] = q[hh].c; // 我们求出的 op[i] 表示每个点的最优决策
if (q[hh].r == i) hh++; // 如果到达了队列的某一项末尾，则决策点改变，即 hh++
q[hh].l = i + 1; // 重新计算 l
insert(i); // 用 i 作为更新决策
}
printf("%lld\n", dp[n]);
return 0;
}
由于四边形不等式优化 DP 的题目不多，而且大部分都较为类似，所以不增加更多例题了。
总结
在做一些决策性 DP 的问题时，如果 v 满足四边形不等式，我们可以考虑四边形不等式优化 DP，复杂度通常会由 O(n^2) 降至 O(n \log n)。如何证明 v 满足四边形不等式？具体的数学证明我们通常不会在做题时证明，有时可以写 O(n^2) 的暴力，对于小数据验证四边形不等式，有时也可以感性理解。四边形不等式本身的性质有许多需要严谨证明的地方，建议自己再推一次。
除此之外，四边形不等式还可以优化决策型区间 DP，例如下面提到的再探石子合并。
例题：P8864 「KDOI-03」序列变换，AcWing 2889. 再探石子合并。
笔者水平有限，若有错误或建议欢迎提出，感谢。