首先介绍四边形不等式 a <= b <= c <= d 用于解决一个对于单调性的神秘不等式
f(i) = 对于所有函数参数范围内的数op(i)
设代价函数为w(i , j) 那么 w(a , c) + w(b , d) <= w(a , d) + w(b , c)
那么我们的f(i)将满足单调性
具体证明是这样的!
第一个反证法:显然,这两个式子唯一影响不等号变化的是b , c。
我们设一个对于w(a , b)的最优解(最大或最小,等等),当然就叫这个东西为p(x)好了
对于c < d 有条件 a = p(d) < p(c) = b 根据这两个条件,我们有 w(a , d) < = w(b , d)
和w(b , c) < w(a , c) 移一下项,我们可以发现有 w(a , d) - w(b , d) <= 0 < w(a , c) - w(b , c)
链接起来会发现与原四边形不等式的变形 w(a , c) - w(b , c) <= w(a , d) - w(b , d)相反,证毕。
第二个则是通过二阶差分,即差分的差分,可以发现,对于具有单调性的w(i , j),他们的差分必须都 > 0
那就再做一遍差分,让这个差分 >= 0再变化变化式子就可以了。