获得另外一种大概会更好的阅读体验
以前看到四边形不等式或叫决策单调性优化dp，看到绕来绕去的式子和繁琐的证明总是望而却步。
数理基础简单打一下后再来看时发现，其实模型就那几个，证明也是比较平平无奇没有什么新奇或难以理解的技巧，故记此文加以巩固，望读者共勉。
部分证明过程会以 Markdown 中引用的格式进行标注，笔者学艺不精还请指出错误及不足之处。
代码大部分是自己口胡出来的，可能写得乱了点。
四边形不等式
设函数 (w(x,y))，其中 (x,y) 整数，若对于任意整数 (a,b,c,d)，满足 (aleq bleq cleq d)，都有 (w(a,c)+w(b,d)leq w(a,d)+w(b,c)) 成立，则称 (w) 满足四边形不等式。
简记为：交叉小于等于包含。
定理一
若对于任意正整数 (a,b)，满足 (a<b)，都有 (w(a,b)+w(a+1,b+1)leq w(a,b+1)+w(a+1,b)) 成立，则 (w) 满足四边形不等式。
我的记法是两步一起蹦跶 （((a,b) o(a+1,b+1))）不如一步一步走远 （((a,b+1),a(a+1,b))），有点像绕口令的感觉了wwwww。
当 (a+1<c) 时，由条件得 (C+Bleq A+D,D+Eleq B+F)，两式相加化简可得 (C+Eleq A+F)，以此类推，对于 (aleq bleq c) 都有 (w(a,c)+w(b,c+1)leq w(a,c+1)+w(b,c)) 成立。
同理，对于所有 (aleq bleq cleq d)，都有 (w(a,c)+w(b,d)leq w(a,d)+w(b,c)) 成立。
1D1D问题的优化
决策单调性：设 (p_i) 为 (f_i) 最优转移的位置（决策点），(p) 单调不降即为具有决策单调性。
一般地，对于 (f_i=min{g_j+w(j,i)}) 的状态转移方程，若 (w) 满足四边形不等式，则 (f) 满足决策单调性。
值得注意的是，这里的 (g_j) 是指的关于 (j) 的函数，其有可能包括 dp 的 (f_j)，也有可能仅包括与 (f_j) 无关的其他 (a_j,b_j,c_j...) 其他关于 (j) 的值，也有可能为常数，但不影响结论的正确性。(min) 还是 (max) 也不影响。
已知 (g_{p_i}+w(p_i,i)leq g_j+w(j,i),j<p_i) 以及 (w) 满足四边形不等式。
求证 (p_{i'}geq p_i,i'>i)。
为了体现想出这个证明的思路，以下的过程表述并不严谨。
(p_{i'}geq p_i) 等价于 (g_{p_i}+w(p_i,i')leq g_j+w(j,i'),j<p_i)。
那么就是想办法把已知条件 (g_{p_i}+w(p_i,i)leq g_j+w(j,i),j<p_i) 中的 (w(p_i,i)) 换成 (w(p_i,i'))，(w(j,i)) 换成(w(j,i’))。
由于 (w) 满足四边形不等式且 (j<p_i<i<i')，
所以 (w(j,i)+w(p_i,i')leq w(p_i,i)+w(j,i'))。
移项得 (w(p_i,i')-w(p_i,i)leq w(j,i')-w(j,i))。
与已知中的不等式相加得到 (g_{p_i}+w(p_i,i)leq g_j+w(j,i),j<p_i)。
故 (p_{i'}geq p)。
考虑维护 (p) 数组，初始全为 (0)，从前往后计算完 (f_i) 时，(f_i) 会更新一个后缀的 (p)。
暴力做这个东西非常完蛋，考虑将 (p) 的一段段连续区间看成一个拿下来放到一个单调栈里，二分单调栈的位置，使得前半部分用 (i) 转移不比之前的 (p) 优，后半部分用 (i) 转移比之前的 (p) 更优，如果需要断开就断开，然后把后缀的都弹出来，压入新的这个后缀。
当然，dp 到 (i) 时 (<i) 的 (p) 是不需要的，所以可以把单调栈改成单调队列。
每次最多只会压入一个点代表的区间，均摊下来，加上二分，时间复杂度是 (mathcal{O}(nlog n)) 的。
栗题一：Luogu P3515 [POI2011]Lightning Conductor
(a_jleq a_i+p_i-sqrt{|i-j|}) 等价于 (p_igeq a_j-a_i+sqrt{|i-j|})。求最小的 (p_i) 使得这个柿子成立，所以 (p_i=max{a_j-a_i+sqrt{|i-j|}})，先钦定 (i>j)，(i<j) 时反过来再做一遍就行。
把 (a_i) 从 (max) 中提出来，把 (a_j) 看成上文中的 (g_j)，也就是关于 (j) 的函数。
由于 dp 中为 (max)，所以需证明 (w(j,i)=-sqrt{i-j}) 满足四边形不等式，即可证明 (p) 的决策单调性，便可以决策单调性优化。
求证：(w(l,r)=-sqrt{r-l}) 满足四边形不等式，即对于任意 (a<b) 均满足 (w(a,b)+w(a+1,b+1)leq w(a,b+1)+w(a+1,b)) 即可。
[ egin{aligned} w(a,b)+w(a+1,b+1)&leq w(a,b+1)+w(a+1,b) \ -sqrt{b-a}-sqrt{(b+1)-(a+1)}&leq -sqrt{(b+1)-a}-sqrt{b-(a+1)} \ 2sqrt{b-a}&geq sqrt{b-a+1}+sqrt{b-a-1} \ ext{设} x=b-a \ 2sqrt{x}&geq sqrt{x+1}+sqrt{x-1} end{aligned} ]注意到 (f(x)=sqrt{x}) 是上凸的，所以由琴生不等式结论得证。
化简到这里，打个表也易知 (2sqrt{x}geq sqrt{x+1}+sqrt{x-1}) 成立。
综上所述，(w) 满足四边形不等式。
实现上要注意用 double 来比较，根号不上取整而是直接开。
因为如果转移点 (j,k) 根号都上取整，在算答案的 (i) 小时大小可能会一样，(i) 变大的时候大小会发生变化。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
typedef long long ll;
typedef double ld;
template <typename T> T Max(T x, T y) { return x > y ? x : y; }
template <typename T> T Min(T x, T y) { return x < y ? x : y; }
template <typename T> T Abs(T x) { return x < 0 ? -x : x; }
template <typename T>
T& read(T& r) {
r = 0; bool w = 0; char ch = getchar();
while(ch < '0' || ch > '9') w = ch == '-' ? 1 : 0, ch = getchar();
while(ch >= '0' && ch <= '9') r = r * 10 + (ch ^ 48), ch = getchar();
return r = w ? -r : r;
}
const int N = 500010;
int n, a[N], qh, qt;
ll f[N];
struct Node {
int l, r, p;
Node(int ll = 0, int rr = 0, int pp = 0) { l = ll; r = rr; p = pp; }
}q[N];
ld w(int x, int y) {
return a[x] - a[y] + std::sqrt(y-x);
}
void solve(int op) {
for(int i = 1; i <= n; ++i) q[i] = Node();
q[qh = qt = 1] = Node(1, n, 1);
for(int i = 1; i <= n; ++i) {
while(qh < qt && q[qh].r < i) ++qh;
if(!op) f[i] = Max(f[i], (ll)std::ceil(w(q[qh].p, i)));
else f[n-i+1] = Max(f[n-i+1], (ll)std::ceil(w(q[qh].p, i)));
if(q[qh].l == q[qh].r) ++qh;
else q[qh].l = i+1;
while(qh <= qt && w(q[qt].p, q[qt].l) < w(i, q[qt].l)) --qt, q[qt].r = q[qt+1].r;
if(qh > qt) q[++qt] = Node(i+1, n, i);
else {
int l = q[qt].l, r = q[qt].r, mid, t = 0;
while(l <= r) {
mid = (l + r) >> 1;
if(w(q[qt].p, mid) < w(i, mid)) t = mid, r = mid-1;
else l = mid+1;
}
if(t) {
if(t == q[qt].l) q[qt].p = i;
else ++qt, q[qt] = Node(t, q[qt-1].r, i), q[qt-1].r = t-1;
}
}
}
}
signed main() {
read(n);
for(int i = 1; i <= n; ++i) read(a[i]);
solve(0);
std::reverse(a + 1, a + n + 1);
solve(1);
for(int i = 1; i <= n; ++i) printf("%lld
", f[i]);
return 0;
}
栗题二：[NOI2009] 诗人小G
设 (f_i) 为考虑前 (i) 个单词的最小代价，枚举 (j)，让 ((j,i]) 的单词分在同一行中。设 (a) 的前缀和为 (s)，可得：
为简化计算，将 (a_i,L) 都 (+1)，得
设 (w(l,r)=|s_r-s_l-L|^p)，证明 (w) 满足四边形不等式则可以决策单调性优化。
求证：对于任意 (a<b) 均满足 (w(a,b)+w(a+1,b+1)leq w(a,b+1)+w(a+1,b)) 即可。
[ egin{aligned} w(a,b)+w(a+1,b+1)&leq w(a,b+1)+w(a+1,b) \ w(a,b)-w(a,b+1)&leq w(a+1,b)-w(a+1,b+1) \ |s_b-s_a-L|^p-|s_{b+1}-s_a-L|^P&leq |s_b-s_{a+1}-L|^p-|s_{b+1}-s_{a+1}-L|^P end{aligned} ]由于 (s_{a+1}>s_a)，设函数 (f(x)=|x|^p-|x-c|^p)，其中 (c) 为 (>0) 的常数，证明其单调不升即可。
分类讨论一下：
假如 (p) 为奇数，并且 (xin [-infty,0])：
化简一下 (f)：(f(x)=-x^p+(x-c)^p)。
求导得 (f'(x)=-px^{p-1}+(p-1)cdot (x-c)^{p-1}leq 0)，所以此时 (f) 单调不升。
其余情况类似，不多赘述，均为化简 (f) 后证明 (f'(x)leq 0) 即可。
如此，我们证明了 (w) 满足四边形不等式，故可以决策单调性优化。
方法就是前面讲过的单调队列 + 二分。注意答案可能很大，开 long double。
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
typedef long double ll;
template <typename T> T Max(T x, T y) { return x > y ? x : y; }
template <typename T> T Min(T x, T y) { return x < y ? x : y; }
template <typename T> T Abs(T x) { return x < 0 ? -x : x; }
template <typename T>
T& read(T& r) {
r = 0; bool w = 0; char ch = getchar();
while(ch < '0' || ch > '9') w = ch == '-' ? 1 : 0, ch = getchar();
while(ch >= '0' && ch <= '9') r = r * 10 + (ch ^ 48), ch = getchar();
return r = w ? -r : r;
}
ll qpow(ll x, int y) {
ll sumq = 1;
while(y) {
if(y & 1) sumq = sumq * x;
x = x * x;
y >>= 1;
}
return sumq;
}
const int N = 100010;
int n, L, P, p[N], a[N], s[N];
int qh, qt;
struct Node {
int p, l, r;
Node(int pp = 0, int ll = 0, int rr = 0) { p = pp; l = ll; r = rr; }
}q[N];
char ch[N][31];
ll f[N];
ll w(int j, int i) {
return f[j] + qpow(Abs(s[i] - s[j] - L), P);
}
void print(int x) {
if(!x) return ;
print(p[x]);
for(int i = p[x]+1; i <= x; ++i) {
printf("%s", ch[i]+1);
if(i < x) putchar(' ');
}
puts("");
}
void solve() {
read(n); read(L); read(P); ++L;
for(int i = 1; i <= n; ++i) {
scanf("%s", ch[i]+1);
a[i] = std::strlen(ch[i]+1);
p[i] = q[i].p = q[i].l = q[i].r = 0;
s[i] = s[i-1] + a[i] + 1;
}
qh = 1; qt = 1;
q[1] = Node(0, 1, n);
for(int i = 1; i <= n; ++i) {
while(qh < qt && q[qh].r < i) ++qh;
f[i] = w(q[qh].p, i); p[i] = q[qh].p;
if(q[qh].l == q[qh].r) ++qh;
else ++q[qh].l;
while(qh <= qt && w(q[qt].p, q[qt].l) > w(i, q[qt].l)) --qt, q[qt].r = q[qt+1].r;
if(qh > qt) q[++qt] = Node(i, i+1, n);
else {
int l = q[qt].l, r = q[qt].r, mid = 0, t = 0;
while(l <= r) {
mid = (l + r) >> 1;
if(w(q[qt].p, mid) > w(i, mid)) t = mid, r = mid-1;
else l = mid+1;
}
if(t) {
if(t == q[qt].l) q[qt].p = i;
else ++qt, q[qt] = Node(i, t, q[qt-1].r), q[qt-1].r = t-1;
}
}
}
if(f[n] > 1000000000000000000ll) {
puts("Too hard to arrange");
return ;
}
printf("%lld
", (long long)f[n]);
print(n);
}
signed main() {
int T; read(T);
while(T--) {
solve();
puts("--------------------");
}
return 0;
}
一点总结
其实大部分的题要点还是能看出来这个满足决策单调性，有时候证不出来也可以打个表看看有没有单调性。
至于栗题的话，如果提前告诉你这个题决策点是单调了从而决策单调性优化，那就没什么意义了，所以就不放啦（其实就是懒