四边形不等式优化DP

Tyne ·

更新时间:2024-11-10

· 755 次阅读

定义 1.原始定义

假设有一个二元函数w(x,y)w(x,y)w(x,y)，如果对于任意a≤b≤c≤da \leq b \leq c \leq da≤b≤c≤d，有

w(a,d)+w(b,c)≥w(a,c)+w(b,d)w(a, d) + w(b, c) \geq w(a, c) + w(b, d)w(a,d)+w(b,c)≥w(a,c)+w(b,d)

就说函数www满足四边形不等式

2.等价定义

还有一个等价的定义：如果对于任意a≤ba\leq ba≤b，有：

w(a,b+1)+w(a+1,b)≥w(a,b)+w(a+1,b+1)w(a, b + 1) + w(a + 1, b) \geq w(a, b) + w(a + 1, b + 1) w(a,b+1)+w(a+1,b)≥w(a,b)+w(a+1,b+1)

就说函数www满足四边形不等式、

证明 2 -> 1

对于任意a<ca < ca<c，有 (1)(1)(1)式：

w(a,c+1)+w(a+1,c)≥w(a,c)+w(a+1,c+1)w(a, c + 1) + w(a + 1, c) \geq w(a, c) + w(a + 1, c + 1)w(a,c+1)+w(a+1,c)≥w(a,c)+w(a+1,c+1)

对于任意a+1,ca+1, ca+1,c，有(2)(2)(2)式：

w(a+1,c+1)+w(a+2,c)>=w(a+1,c)+w(a+2,c+1)w(a + 1, c + 1) + w(a + 2, c) >= w(a + 1, c) + w(a + 2, c + 1)w(a+1,c+1)+w(a+2,c)>=w(a+1,c)+w(a+2,c+1)

两式相加得到(3)(3)(3)式：

w(a,c+1)+w(a+2,c)≥w(a,c)+w(a+2,c+1)w(a, c + 1) + w(a + 2, c) \geq w(a, c) + w(a + 2, c + 1)w(a,c+1)+w(a+2,c)≥w(a,c)+w(a+2,c+1)

对比(1)(1)(1)式和(3)(3)(3)式，发现a+1a + 1a+1可以扩成a+2a + 2a+2，同理a+2a+2a+2可以扩成a+3a+3a+3，a+3a+3a+3可以扩成a+4a+4a+4……可以一直扩大直至b≤cb\leq cb≤c（bbb是在aaa和ccc之间的一个数），从而得到：

w(a,c+1)+w(b,c)≥w(a,c)+w(b,c+1)w(a, c + 1) + w(b, c) \geq w(a, c) + w(b, c + 1)w(a,c+1)+w(b,c)≥w(a,c)+w(b,c+1)

同理，对于任意a<c+1a<c+1a<c+1，有(4)(4)(4)式：

w(a,c+2)+w(a+1,c+1)≥w(a,c+1)+w(a+1,c+2)w(a, c + 2) + w(a + 1, c + 1) \geq w(a, c + 1) + w(a + 1, c + 2)w(a,c+2)+w(a+1,c+1)≥w(a,c+1)+w(a+1,c+2)

(1)(1)(1)式与(4)(4)(4)式相加得到(5)(5)(5)式：

w(a,c+2)+w(a+1,c)≥w(a,c)+w(a+1,c+2)w(a, c + 2) + w(a + 1, c) \geq w(a, c) + w(a + 1, c + 2)w(a,c+2)+w(a+1,c)≥w(a,c)+w(a+1,c+2)

与(1)(1)(1)式进行一下直观对比：

(1)(1)(1)式：w(a,c+1)+w(a+1,c)≥w(a,c)+w(a+1,c+1)w(a, c + 1) + w(a + 1, c) \geq w(a, c) + w(a + 1, c + 1)w(a,c+1)+w(a+1,c)≥w(a,c)+w(a+1,c+1)

(5)(5)(5)式：w(a,c+2)+w(a+1,c)≥w(a,c)+w(a+1,c+2)w(a, c + 2) + w(a + 1, c) \geq w(a, c) + w(a + 1, c + 2)w(a,c+2)+w(a+1,c)≥w(a,c)+w(a+1,c+2)

可以发现c+1c+1c+1可以扩成c+2c+2c+2，同理c+2c+2c+2可以扩成c+3c+3c+3，c+3c+3c+3可以扩成c+4c+4c+4……可以一直扩大一直到d(c≤d)d(c\leq d)d(c≤d)，从而得到：

w(a,d)+w(a+1,c)≥w(a,c)+w(a+1,d)w(a,d) + w(a + 1, c) \geq w(a, c) + w(a + 1, d)w(a,d)+w(a+1,c)≥w(a,c)+w(a+1,d)

再把上式a+1a+1a+1扩大到bbb，保证a≤b≤c≤da\leq b \leq c \leq da≤b≤c≤d，就可以得到111，即

w(a,d)+w(b,c)≥w(a,c)+w(b,d)w(a,d) + w(b, c) \geq w(a, c) + w(b, d)w(a,d)+w(b,c)≥w(a,c)+w(b,d)

由此原始定义得证。

所以，证了这么久有啥用呢？

决策单调性

我们在做DPDPDP时经常会遇见这样的DPDPDP方程

dp[i]=min⁡/max⁡{dp[j]+cost(j,i)}dp[i] = \min/\max\{dp[j] + cost(j, i)\}dp[i]=min/max{dp[j]+cost(j,i)}

这样的DPDPDP方程被称作1D/1D1D/1D1D/1D动态规划，cost(i,j)cost(i,j)cost(i,j)决定着优化策略选择

决策单调性定理

如果函数cost(i,j)cost(i,j)cost(i,j)满足四边形不等式，则dp[i]dp[i]dp[i]有决策单调性（充分条件）

证明：

注：假设此时已经满足四边形不等式

假设此时的DPDPDP方程为dp[i]=min⁡{dp[j]+cost(j,i)}dp[i] = \min\{dp[j] + cost(j, i)\}dp[i]=min{dp[j]+cost(j,i)}，dp[i]dp[i]dp[i]的决策点是p[i]p[i]p[i]，对于j<p[i]−1(j<i)j < p[i] - 1(j < i)j<p[i]−1(j<i)，根据最优性：

dp[p[i]]+cost(p[i],i)≤dp[j]+cost(j,i)dp[p[i]] + cost(p[i], i) \leq dp[j] + cost(j, i)dp[p[i]]+cost(p[i],i)≤dp[j]+cost(j,i)

假设i′>ii' > ii′>i，此时j≤p[i]≤i≤i′j \leq p[i] \leq i \leq i'j≤p[i]≤i≤i′，根据四边形不等式：

cost(j,i′)+cost(p[i],i)≥cost(j,i)+cost(p[i],i′)cost(j, i') + cost(p[i], i) \geq cost(j, i) + cost(p[i], i')cost(j,i′)+cost(p[i],i)≥cost(j,i)+cost(p[i],i′)

对这个式子进行移项，得到

cost(p[i],i′)−cost(p[i],i)≤cost(j,i′)−cost(j,i)cost(p[i], i') - cost(p[i], i) \leq cost(j, i') - cost(j, i)cost(p[i],i′)−cost(p[i],i)≤cost(j,i′)−cost(j,i)

将此式和DPDPDP式（根据最优性得出的式子）相加得：

dp[p[i]]+cost(p[i],i′)≤dp[j]+cost(j,i′)dp[p[i]] + cost(p[i], i') \leq dp[j] + cost(j, i')dp[p[i]]+cost(p[i],i′)≤dp[j]+cost(j,i′)

由此可得，对于i′i'i′来说，p[i]p[i]p[i]比jjj优，得证。

小小结

在上面的证明中我们可以知道，等价定义可以推出原始定义，而原始定义又可以推出决策单调性定理，其实在日常做题中，如果满足了等价定义，我们就可以直接用决策单调性来解决问题（就是说222可以推出111，111可以推出333，那么222可以推出333）

下面就来看一道例题吧

例题

链接：洛谷P3515 [POI2011]Lightning Conductor

题目很简洁，就是为了找这么一个数ppp满足题目中给出的式子

那么我们不妨先移项，得到如下的式子

p≥a[j]−a[i]+∣i−j∣p\geq a[j] - a[i] + \sqrt{|i - j|}p≥a[j]−a[i]+∣i−j∣

而此时我们又要找到满足条件的最小的ppp

所以此时的ppp只要等于后面这个式子的最大值即可，即

p=max⁡(a[j]−a[i]+∣i−j∣),1≤j≤np = \max(a[j] - a[i] + \sqrt{|i - j|}), 1\leq j \leq np=max(a[j]−a[i]+∣i−j∣),1≤j≤n

先考虑一种比较好的情况，假设j<ij<ij<i，那么绝对值就可以去掉了，即

p=max⁡(a[j]+i−j)−a[i]p = \max(a[j] + \sqrt{i - j}) - a[i]p=max(a[j]+i−j)−a[i]

上式中max⁡\maxmax里的式子取到最大值，相当于负的这个式子取到最小值

所以我们可以定义dp[i]=min⁡(−a[j]−i−j)dp[i] = \min(-a[j] - \sqrt{i - j})dp[i]=min(−a[j]−i−j)

为什么要用min⁡\minmin呢，因为在上面的证明中我们使用的都是min⁡\minmin，所以这里是用min⁡\minmin，如果是max⁡\maxmax的话可以换成负数取个min⁡\minmin就好了，这是一样的，反正dp[i]dp[i]dp[i]是自己定义的，定义成正负都一样

但是这样直接做是n2n^2n2的，这不能达到我们的要求，所以现在我们来进行优化

观察一下这个DPDPDP方程的二元函数，那么此时的w(j,i)w(j,i)w(j,i)就等于−a[j]−i−j-a[j] - \sqrt{i - j}−a[j]−i−j

为了进行优化，下一步我们证明一下这个DPDPDP能不能满足决策单调性

求证：w(j,i+1)+w(j+1,i)≥w(j,i)+w(j+1,i+1)w(j, i+ 1) + w(j + 1, i) \geq w(j, i) + w(j + 1, i + 1)w(j,i+1)+w(j+1,i)≥w(j,i)+w(j+1,i+1)

证明：

把式子展开得

−a[j]−i+1−j−a[j+1]−i−j−1≥−a[j]−i−j−a[j+1]−i−j-a[j] - \sqrt{i + 1 - j} - a[j + 1] - \sqrt{i - j - 1} \geq -a[j] - \sqrt{i - j} - a[j + 1] - \sqrt{i - j}−a[j]−i+1−j−a[j+1]−i−j−1≥−a[j]−i−j−a[j+1]−i−j

发现可以去掉带有aaa数组的部分，然后式子就变成了这样

−i+1−j−i−j−1≥−i−j−i−j-\sqrt{i + 1 - j} - \sqrt{i - j - 1} \geq -\sqrt{i - j} - \sqrt{i - j}−i+1−j−i−j−1≥−i−j−i−j

移一下项得

i−j−i−j−1≥i+1−j−i−j\sqrt{i - j} - \sqrt{i - j - 1} \geq \sqrt{i + 1 - j} - \sqrt{i - j} i−j−i−j−1≥i+1−j−i−j

令x=i−jx = i - jx=i−j，因为i>ji > ji>j ，所以x>0x>0x>0，于是一开始那个繁琐的问题就变成了证明x−x−1≥x+1−x\sqrt{x} - \sqrt{x - 1} \geq \sqrt{x + 1} - \sqrt{x}x−x−1≥x+1−x

定义函数f(x)=x−x−1f(x)=\sqrt{x} - \sqrt{x - 1}f(x)=x−x−1，问题又转化成了证明f(x)≥f(x+1)f(x) \geq f(x + 1)f(x)≥f(x+1)，那么就是要证明f(x)f(x)f(x)是单调非递增的函数即可

懒得证单调性……自己搜吧qwqqwqqwq

因为是个单调递减函数，所以证明成功

j>ij>ij>i时可以把序列翻转，得到的结果是一样的，做题的时候将序列翻转反向再做一遍上述操作即可，就不证明了

代码鸽了

总结

因为我很辣鸡，所以只能写这么一点点了qwqqwqqwq