【教程】四边形不等式学习笔记

前言

　　四边形不等式是一种动态规划优化方法，通过对决策单调性的证明及应用，使得总体复杂度降低一个数量级。目前我见过的四边形不等式的题目不多，且大多数比较裸。四边形不等式的常见模型及其基础应用并不难，难点在于与四边形不等式相关的证明，尤其是题目中出现以前没有见过的转移方程的时候。由于本人数学很渣，所以问了很多大神，尝试了各种方法绕过证明。这里把我的经验分享给大家，尤其是像我一样的数学不好的同学。所以，本文并没有证明相关的东西，如果大家想看证明，可以阅读赵爽的文章《动态规划加速原理之四边形不等式》，百度文库上应该有免费下载。

一种基本形式

　　四边形不等式的基本形式非常简单，用于常见的区间dp的优化。

　　转移方程形式为f[i][j] = min{ f[i][k] + f[k+1][j] + w(i,j) | i <= k < j }。

　　这个方程大家再熟悉不过了，长区间可以从短区间转移过来，w(i,j)表示将闭区间[i,j]合并产生的费用，状态有O(n^2)个，每个状态的决策有O(n)个，总复杂度为O(n^3)。

　　现在用四边形不等式对其优化，首先需要知道什么是四边形不等式。

　　若函数w(i,j)满足w(a,c) + w(b,d) <= w(a,d) + w(b,c)，其中a <= b < c <= d，则称w满足四边形不等式。可以看做一个以(a,c)为左上角，(b,d)为右下角的矩阵中，左上角的值加上右下角的值小于左下角的值加上右上角的值。注意我们要求b < c，因为在实际的区间问题中，既然w(b,c)表示合并区间[b,c]的费用，那么b一定是小于等于c的。在这个限制下，如果把我们所有的状态写成一个矩阵的话，有用的状态一定是行号小于等于列号的，即所有有用的状态f[i][j]中，i <= j。

　　若函数w(i,j)满足w(a,d) >= w(b,c)，其中a <= b <= c <= d，则称w关于区间包含关系单调。可以看做长区间的值大于等于它包含的短区间的值。

　　设使f[i][j]取到最小值的k为p[i][j]，即在方程f[i][j] = min{ f[i][k] + f[k+1][j] + w(i,j) | i <= k < j }中，k = p[i][j]时，f[i][j]取到最小值。

　　那么有如下定理：

　　1.若w满足四边形不等式，且关于区间包含关系单调，则f也满足四边形不等式。

　　2.若f满足四边形不等式，则p[i][j-1] <= p[i][j] <= p[i+1][j]，即如果把p看做一个矩阵的话，p在每一行上单调非降，在每一列上单调非降。

　　3.w满足四边形不等式，当且仅当w(i,j) + w(i+1,j+1) <= w(i+1,j) + w(i,j+1)。

　　这三个定理我就不在这里证明了，大家可以去看前言中提到的那篇论文。其中第三个定理可以用来证明w满足四边形不等式，我们主要使用第二个定理优化dp。

　　具体如何优化呢？我们原来在计算f[i][j]的时候，枚举的k值范围是[i,j)，所以单次转移的复杂度是O(n)，现在，我们既然知道了p[i][j-1] <= p[i][j] <= p[i+1][j]，我们只需要把k的枚举范围改成p[i][j-1]至p[i+1][j]就好了！总体复杂度就变成了O(n^2)了！注意这里是闭区间，即p[i][j-1]和p[i+1][j]都能取到。下面给出简单证明。

　　对于固定的区间长度len，有

　　f[i][i+len]的决策范围为p[i][i+len-1]至p[i+1][i+len]

　　f[i+1][i+len+1]的决策范围为p[i+1][i+len]至p[i+2][i+len+1]

　　f[i+2][i+len+2]的决策范围为p[i+2][i+len+1]至p[i+3][i+len+2]

　　如此脑补下去，我们发现，对于固定的区间长度len，总共的决策只有O(n)个！因为一共有O(n)个不同的区间长度len，所以算法的总复杂度就是O(n^2)！

　　我们干了什么？首先需要证明w满足四边形不等式，然后只需要记录一下每个f[i][j]的决策点，并且改一下k的枚举范围，就能把时间复杂度降一个量级。

如何绕过证明

　　四边形不等式优化代码十分简单，且效果也很好，但是最令人头疼的就是如何证明w满足四边形不等式。

　　有可能这个对大家还比较容易，但是要知道，满足这些性质的转移方程不止这一种！对于f[i][j] = min{ f[i-1][k] + w(k+1,j) | i-1 <= k < j }这个方程来说，若w满足四边形不等式，f同样满足四边形不等式，也可以使用决策单调性优化，但是证明就比较困难了。YJQ教给我一种很好的绕过证明使用四边形不等式的方法，但是使用起来不是那么简单，有一些注意事项。下面的内容可就是别人博客里没有的东西了！

　　大致方法很简单，如果我们觉得一个方程能用四边形不等式优化，就把他的所有决策点，也就是p矩阵打印出来，观察一下在每行每列上是否单调，如果单调，就说明这个方程可以用四边形不等式优化。不过需要小心一些地方。

　　首先，注意决策点应该在哪些范围之内单调，比如对于区间dp的方程来说，决策点的单调范围就应该是行号小于等于列号的那一部分。这点在实际问题中应该很容易体现出来，比如对于区间dp，行号大于列号的那些状态肯定是无用的，决策单调性也肯定不关它们什么事。

　　其次，应该注意递推时枚举的顺序和状态之间的依赖关系。比如对于上面那个方程来说，决策矩阵p在每行每列单调递增，所以应该把k的枚举范围该成p[i-1][j]至p[i][j+1]，注意这里和区间dp就不一样了，所以应该根据状态之间的依赖关系灵活调整枚举范围。而且，如果我们遵循这样的依赖关系，就应该有p[i][j]依赖于p[i][j+1]，所以k应该从大到小倒着枚举。

　　而且，能不能用四边形不等式优化貌似还和状态定义，和转移方程有关。所以可能会出现某种状态定义可以优化而另外一种不能的情况？我还没遇到过（已经开始口胡了）。。。

总结

　　其实四边形不等式虽然很神，但是题目不算多，转移方程也就那么几种，特征也比较明显。至于定理什么的，实在不会证明记住就好了，然后检验决策单调性的话就打个表，毕竟OI中不需要我们会证明的东西还不是一抓一大把（逃）。

　　顺便说一下，与四边形不等式相关的优化，还有一个叫凸完全单调性，也是证明之后利用决策单调性优化。这个我不会，大家可以去百度文库搜杨哲的ppt《凸完全单调性的加强与应用》看看。

习题（转自他人博客）

　　Lawrence HDU 2829

　　Post Office IOI 2000 POJ 1160

　　Monkey Party HDU 3506

参考资料

　　刘汝佳《算法艺术与信息学竞赛》

今天的文章【教程】四边形不等式学习笔记分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。