四边形不等式 / 决策单调性
真正用于优化的性质是决策单调性：对于任意决策点 \(p\)，如果 \(i\) 处从 \(p\) 转移都优于从 \(p\) 前转移，则任意大于 \(i\) 的位置 \(i'\) 从 \(p\) 转移都优于从 \(p\) 前转移。
四边形不等式是常见的证明决策单调性的方法。
虽然场上建议打表找规律直接猜
四边形不等式优化 \(f_{i} = \min_{j < i} (F(j) + w(j, i))\)。
\(w(j, i)\) 是区间的代价。
如果 \(w(j, i)\) 满足对于任意 \(a \le b \le c \le d\) 都满足 \(w(a, c) + w(b, d) \le w(a, d) + w(b, c)\)。
则称 \(w(j, i)\) 满足四边形不等式（交叉小于包含）。
上述判断条件等价于
对于任意 \(i < i + 1 \le j < j + 1\)
都满足 \(w(i, j) + w(i + 1, j + 1) \le w(i, j + 1) + w(i + 1, j)\)，
这个式子只有两个元多用于四边形不等式证明。
如果 \(w(j, i)\) 满足四边形不等式则转移具有决策单调性。
利用决策单调性，可以从前往后 dp，时刻维护每个位置的最优决策点 \(p_i\)。
在转移 \(i\) 时直接从 \(p_i\) 转移，然后以 \(i\) 为决策点去更新后面的 \(p\)。
由于决策单调性，那么 \(p\) 任意时刻单调不降。
那么可以想到，\(p\) 可以划分成若干区间，每个区间内决策点相同，在用决策点 \(i\) 更新 \(p\) 时，\(i\) 占据的区间一定是一个后缀（因为 \(i\) 是当前所有决策点里最大的）。
那么 \(i\) 可以从后往前检查每个区间的左端点，如果 \(i\) 更优，直接把这个区间删掉，否则，说明分界点在这个区间内部，可以二分出分界点，从分界点一直到结尾在当前 \(i\) 都是最优决策。
对于上述区间，由于我们处理的 \(i\) 是单调后移的，所以如果一个区间的右端点已经小于 \(i\) 了，那么它彻底没用了，可以直接删掉。
所以可以双端队列维护这些区间。
复杂度：由于每个决策点只会进出队列一次，所以进出队列复杂度均摊 \(O(1)\)，由于在入队时需要二分分界点，所以转移总复杂度 \(O(\log n)\)（默认 \(w\) 可以 \(O(1)\) 计算）。
或者其实不用维护每个决策点的左端点，直接在队列里相邻两个决策点二分找后一个决策点左端点也可以。复杂度不变。
好像这个的模板还挺通用：
// Calc(j, i) = F(j) + w(j, i)
// 求 x 决策点 和 y 决策点的范围的分界点，返回 y 范围的左端点
int get(int x, int y) {
int l = y, r = n + 1, res = n + 1;
while (l <= r) {
int mid = l + r >> 1;
if (Calc(x, mid) >= Calc(y, mid)) // 这里的大小关系依据题面定
res = mid, r = mid - 1;
else
l = mid + 1;
}
return res;
}
//...
for (int i = 1; i <= n; ++i) {
while (hed < tal && get(q[hed], q[hed + 1]) <= i) ++hed;
f[i] = Calc(q[hed], i);
while (hed < tal && get(q[tal - 1], q[tal]) >= get(q[tal], i)) --tal;
q[++tal] = i;
}
P1912
诗人小 G，年轻人不知道是不是第一款打表找规律决策单调性题。
\(w(j, i) = |sum_i - sum_j - (i - j - 1) - L|^P\)
然后代上面那个两个元的式子小力分类讨论 \(P\) 分奇偶再零点分段去绝对值什么的就可以得到 \(w\) 在任意时候满足四边形不等式。
然后直接做。
P3515 / P5503 / SP9070
纯三倍经验。
得到 \(p \ge a_j\)
标签：le,22,不等式,24.12,决策,区间,四边形,单调 From： https://www.cnblogs.com/KinNa-Sky/p/18622541