算法竞赛专题解析│四边形不等式优化( 三 ) ：算法竞赛专题解析│四边形

c(i,j)+c(j,j′)≤c(i,j′)i<j<j′(6?4)
现在证明公式(6-4) 。
假设c(i,j′)在k=z处有最小值，即c(i,j′)=cz(i,j′) 。这里定义ck(i,j)等于w(i,j)+c(i,k?1)+c(k,j) 。
有2个对称情况A1)和A2) 。
caseA1).z≤j
z是(i,j′)区间的最优点，不是(i,j)区间的最优点，所以有：
c(i,j)≤cz(i,j)=w(i,j)+c(i,z?1)+c(z,j)
在两边加上c(j,j′)：
c(i,j)+c(j,j′)≤w(i,j)+c(i,z?1)+c(z,j)+c(j,j′)
≤w(i,j′)+c(i,z?1)+c(z,j′)
=c(i,j′)
上面的推导时利用了下面2条：
1)w的单调性，有w(i,j)≤w(i,j′)；
2)公式(6-4)的归纳假设：假设z≤j≤j′时成立，递推出i<j<j′时公式(6-4)也成立。观察下面的图，有c(z,j)+c(j,j′)≤c(z,j′) ，它满足反三角形不等式。

文章图片
▍图4储枫论文图-引理1的caseA1
caseA2).z≥j 。是A1)的对称情况。
caseB).i<i′<j<j′
假设公式(6-3)右边的小区间c(i′,j)和大区间c(i,j′)分别在k=y和k=z处有最小值，记为：
c(i′,j)=cy(i′,j)
c(i,j′)=cz(i,j′)
同样有2个对称情况B1)和B2) 。
caseB1).z≤y
有c(i′,j′)≤cy(i′,j′)
和c(i,j)≤cz(i,j)
两式相加得：
c(i,j)+c(i′,j′)
≤cz(i,j)+cy(i′,j′)
=w(i,j)+w(i′,j′)+c(i,z?1)+c(z,j)+c(i′,y?1)+c(y,j′)(6?5)
公式(6-5)的进一步推导利用了下面2条：
1)根据w的四边形不等式，有w(i,j)+w(i′,j′)≤w(i′,j)+w(i,j′)；
2)根据公式(6-3)的归纳假设，即假设z≤y<j<j′时成立。观察下图，有c(z,j)+c(y,j′)≤c(y,j)+c(z,j′) ，满足反四边形不等式。

文章图片
▍图5储枫论文图-引理1的caseB1
则公式(6-5)变为：
c(i,j)+c(i′,j′)
≤w(i′,j)+w(i,j′)+c(i,z?1)+c(i′,y?1)+c(y,j)+c(z,j′)
≤cy(i′,j)+cz(i,j′)
=c(i′,j)+c(i,j′)
caseB2).z≥y 。是B1)的对称情况。
引理1证毕。
2.证明引理2
用Kc(i,j)表示max{k∣ck(i,j)=c(i,j)} ，也就是使c(i,j)得到最小值的那些k中，最大的那个是Kc(i,j) 。定义Kc(i,i)=i 。 Kc(i,j)就是前面例子中的s[i][j] 。
引理2：Kc(i,j)≤Kc(i,j+1)≤Kc(i+1,j+1)(6?6)
下面是证明。
i=j时显然成立，下面假设i<j 。
先证明公式(6-6)的第一部分Kc(i,j)≤Kc(i,j+1) 。这等价于证明：对于i<k≤k′≤j ，有
ck′(i,j)≤ck(i,j)?ck′(i,j+1)≤ck(i,j+1)(6?7)
公式(6-7)的意思是：如果ck′(i,j)≤ck(i,j)成立，那么ck′(i,j+1)≤ck(i,j+1)也成立。 ck′(i,j)≤ck(i,j)的含义是，在[i,j]区间， k′是比k更好的分割点，可以把k′看成[i,j]的最优分割点。扩展到区间[i,j+1]时，有ck′(i,j+1)≤ck(i,j+1) ，即k仍然是比k更好的分割点。也就是说，区间[i,j+1]的最优分割点肯定大于等于k′ 。
下面证明公式(6-7) 。
根据四边形不等式，在k≤k′≤j<j+1时，有
c(k,j)+c(k′,j+1)≤c(k′,j)+c(k,j+1)
在两边加上w(i,j)+w(i,j+1)+c(i,k?1)+c(i,k′?1) ，得：
ck(i,j)+ck′(i,j+1)≤ck′(i,j)+ck(i,j+1)
把ck(i,j)移到右边：
ck′(i,j+1)≤ck′(i,j)+ck(i,j+1)?ck(i,j)(6?8)
把(6-7)的ck′(i,j)≤ck(i,j)的两边加上ck(i,j+1)：
ck′(i,j)+ck(i,j+1)≤ck(i,j)+ck(i,j+1)
ck′(i,j)+ck(i,j+1)?ck(i,j)≤ck(i,j+1)
结合(6-8) ，得ck′(i,j+1)≤ck(i,j+1) ，公式(6-7)成立。
同样可以证明，公式(6-6)的右半部分Kc(i,j+1)≤Kc(i+1,j+1) ，在i<i+1≤k≤k′时成立。
引理2说明当i、j增大时， Kc(i,j)是非递减的。
3.证明四边形不等式定理
利用引理2 ，可推论出四边形不等式定理，即用DP计算所有的c(i,j)的时间复杂度是O(n2)的。下面对这一结论进行说明。
用DP计算c(i,j)时，是按δ=j?i=0,1,2,...,n?1的间距逐步增加进行递推计算的。具体过程请回顾前面第2节求dp[i][j]的代码。从c(i,j)递推到c(i,j+1)时，只需要Kc(i+1,j+1)?Kc(i,j)次最少限度的操作就够了。总次数是多少呢？对一个固定的δ ，计算所有的c(i,j) ， 1≤i≤n?δ ， j=i+δ ，次数是：
i=1时：Kc(1+1,1+δ+1)?Kc(1,δ+1)=Kc(2,δ+2)?Kc(1,δ+1)
i=2时：Kc(2+1,2+δ+1)?Kc(2,δ+2)=Kc(3,δ+3)?Kc(2,δ+2)
i=3时：Kc(3+1,3+δ+1)?Kc(3,δ+3)=Kc(4,δ+4)?Kc(3,δ+3)
…
i=n?δ时：Kc(n?δ+1,n?δ+δ+1)?Kc(n?δ,δ+n?δ)=Kc(n?δ+1,n+1)?Kc(n?δ,n)
以上式子相加，次数=Kc(n?δ+1,n+1)?Kc(1,δ+1) ，小于n 。
对一个δ ，计算次数是O(n)的；有n个δ ，总计算复杂度是O(n2)的。
以上证明了四边形不等式定理。
4.min和max
前面讨论的都是min ，如果是max ，也可以进行四边形不等式优化。此时四边形不等式是“反”的：