1.定义
1.1 四边形不等式
四边形不等式指的是二元函数 \(w(l,r)\) 对于 \(l_1 \le l_2 \le r_1 \le r_2\) 满足：
\[w(l_1, r_1) + w(l_2, r_2) \le w(l_2, r_1) + w(l_1, r_1) \]也就是交叉优于包含。
四边形不等式的等价形式是：
\[w(l, r - 1) + w(l + 1, r) \le w(l, r) + w(l + 1, r - 1) \]常见的满足四边形不等式的函数包括几类：
-
\(w(l,r) = f(l) - g(r)\)，显然不等号会去等。常见的有前缀和。
-
\(w(l,r) = f(a_r - a_l)\)，其中 \(a_1 < a_2 < \dots < a_n\) 且 \(f\) 是凸函数（也就是二阶差分非负）。比如 \(f(x) = x^p(p > 1)\) 和 \(f(x) = -x^p(0 < p < 1)\)。
-
两个函数分别满足四边形不等式，则它们的和也满足。
1.2 单调性
如果函数 \(w(l,r)\) 满足：
\[\forall l' \le l \le r \le r', w(l,r) \le w(l', r') \]则其满足区间包含单调性。
对于一个动态规划来说，我们记录其最优决策点集合中最小的元素为 \(opt\)，下面记为最优决策点（注意一定要取最小的或者最大的）。
我们假设下面的函数计算都是 \(O(1)\) 的，且都满足四边形不等式。
2. 离线版本
考虑转移方程：
\[f(i) = \min_{1 \le j < i}\{w(j,i)\} \]直接暴力是 \(O(n^2)\)，我们考虑如何在 \(O(n \log n)\) 内计算。
我们定义 \(opt(i)\) 是 \(f_i\) 的最优决策点。我们可以证明若 \(i \le i'\)，则 \(opt(i) \le opt(i')\)，也就是其具有决策单调性。
证明不难，oi-wiki 上有。
所以我们现在考虑分治计算：取中点 \(m\)，我们先算出 \(f(m),opt(m)\)，然后递归计算两边的值。考虑到两边的 \(opt\) 集合被一分为二，所以每一层的总计算量都是 \(O(n)\) 的，总共 \(\log n\) 层，时间复杂度 \(O(n \log n)\)。
模板题 P3515 [POI2011] Lightning Conductor。
这道题转化一下就是 \(w(l,r) = a_r- a_l - \sqrt{|r - l|}\)。
这个函数的前半部分属于四边形不等式的函数类的第一种，后半部分属于第二种，所以这个函数满足四边形不等式。
然后我们就可以用分治求解了：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5e5 + 5;
int n, h[N] = {0};
double w(int j, int i) {
return h[j] - h[i] + sqrt(i - j);
}
void slv(int *f, int l, int r, int pl, int pr) {
if (l > r)
return;
int mid = (l + r) / 2, p = pl;
for (int i = pl + 1; i <= min(mid - 1, pr); i++)
if (w(i, mid) > w(p, mid))
p = i;
f[mid] = max(f[mid], (int)ceil(w(p, mid)));
slv(f, l, mid - 1, pl, p);
slv(f, mid + 1, r, p, pr);
}
int f[N] = {0};
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &h[i]);
slv(f, 1, n, 1, n);
reverse(h + 1, h + n + 1);
reverse(f + 1, f + n + 1);
slv(f, 1, n, 1, n);
for (int i = 1; i <= n; i++)
printf("%d\n", f[n - i + 1]);
return 0;
}
3. 1D-1D 在线版本
求：
\[f(i) = \min_{1 \le j < i}\{f(j) + w(j,i)\} \]考虑到 \(f(j) + w(j,i)\) 显然也是满足四边形不等式的，所以决策单调性依然存在，但是由于我们依赖前面的结果，所以我们不能用分治来求解了。
这里我们用的方法是二分队列。
我们考虑决策点的值。
刚开始所有都是 0，然后我们加入 1 后一段后缀会变成 1，加入 2 后一段比之前后缀会变成 2，以此类推。
我们用队列存储 \((l,r,p)\) 表示当前 \([l,r]\) 的最优决策点都是 \(p\)，一开始只有 \((1,n,0)\)，我们假设现在计算 \(i\)。
首先，我们计算 \(f(i)\)，显然其最优决策点就是现在的队首。
计算完之后，我们先判断队首是否为空，如果为空就弹出。
然后我们开始和队尾比较，每次看
标签：le,不等式,int,mid,笔记,四边形,include From： https://www.cnblogs.com/rlc202204/p/18385231