最长公共上升子序列的另一个O(mn)的算法

2006 年 10 月 18 日 / 30 条评论

    我在这个帖子里说过nlogn求最长上升子序列的方法：
    http://www.oibh.org/bbs/viewthread.php?tid=10682
    下面引用我自己的发言：

     f表示长度为i的上升子序列最后一个数最小是多少。显然数组f是单增的。
     读到一个新的数x后，找到某个i使得x>f[i]且x<=f[i+1]，于是用x去更新f[i+1]；特别地，如果所有的f[i]都小于x，则增加f的长度。
     最后看f数组有多长就行了。
     由于f单增，所以查找i时可以用二分查找，因此时间复杂度为O(nlogn)。
     举个例子，假如序列为 3 2 8 6 7 4 5 7 3，则f数组的变化过程如下：
     3
     2
     2 8
     2 6
     2 6 7
     2 4 7
     2 4 5
     2 4 5 7
     2 3 5 7
     最后，f的长度达到4，因此答案为4。
     注意，最后的f数组不一定是最长上升子序列的一个方案。

这里要说的这个算法利用了nlogn的最长上升子序列(LIS)的技巧：用f[k]表示长度为k的上升子序列最后一个数最小是多少。
在最长公共上升子序列中，令f[i,j][k]表示A串前i个数字，B串前j个数字，长度为k的公共上升子序列中，最后一个数最小是多少。

    当A[i]=B[j]时，像nlogn的最长上升子序列一样把A[i]插入到f[i-1,j]中，这需要线性的时间扫一遍f[i,j]；
    当A[i]<>B[j]时，我们需要合并f[i-1,j]和f[i,j-1]，使得对于每个k满足f[i,j][k]:=min{ f[i-1,j][k],f[i,j-1][k] }。这需要线性的时间扫一边f[i-1,j]和f[i,j-1]并取k相同时的较小值。
    最后输出f[n,m]的长度（使f[n,m][k]有意义的最大的k）。
    这样的复杂度是三方的，我们需要优化。

    考虑A[i]=B[j]的情况。当i固定时，随着j的增加，插入的位置一定也在后移，因为同样是插入的A[i]，但j的增加（B串长度的增加）使得f [i,j]更优，因此可以更新的值就更靠后。于是，对于每个i，我们可以按照k的顺序扫描f[i-1,j][k] 并在A[i]可以插入f[i-1][j]的k位置时增加j，从而预处理所有A[i]=B[j]时A[i]应该插入的位置。
    再考虑A[i]<>B[j]的情况。从定义看，f[i-1,j-1]和f[i-1,j]只有一个地方不一样，因为多一个数最多只能造成一个k 的值变小；同样地，f[i-1,j-1]和f[i,j-1]也只有一个地方不一样。因此，f[i-1,j]和f[i,j-1]最多只有两个k所对应的值不相同，且当有两个不同的值时，总是f[i-1,j]中的某个值较小，f[i,j-1]中的某个值较小。这给我们优化的余地。在每次处理完f[i,j]时，我们可以记录一个值x[i,j]表示f[i,j][k]与f[i-1,j][k]中值不一样的k是多少，在A[i]=B[j]时直接赋值为插入的位置，在 A[i]<>B[j]时待后文说明。以后合并时，先让f[i,j]:=f[i-1,j]（由于此时的f[i-1,j]已经没有别的用处了，因此可以用滚动数组记录，直接令f[i-1,j]是f[i,j]，避免实际的赋值操作），然后将新的f[i,j]中的，使f[i,j-1][k]比f[i- 1, j][k]小的k所对应值更新。这个k是多少呢？显然应该是x[i,j-1]。这样的操作同时可以确定x[i,j]=x[i,j-1]。
    这样，复杂度就达到了平方。

附参考的资料（原来从这篇论文里学到的，不知道有没有此类的中文资料，估计没有才在这里写了一个，感兴趣的话可以下载附件仔细研究）

点击下载此文件

Matrix67原创
转载请注明出处

什么是离散化？

2006 年 9 月 26 日 / 42 条评论

如果说今年这时候OIBH问得最多的问题是二分图，那么去年这时候问得最多的算是离散化了。对于“什么是离散化”，搜索帖子你会发现有各种说法，比如“排序后处理”、“对坐标的近似处理”等等。哪个是对的呢？哪个都对。关键在于，这需要一些例子和不少的讲解才能完全解释清楚。
离散化是程序设计中一个非常常用的技巧，它可以有效的降低时间复杂度。其基本思想就是在众多可能的情况中“只考虑我需要用的值”。下面我将用三个例子说明，如何运用离散化改进一个低效的，甚至根本不可能实现的算法。

    《算法艺术与信息学竞赛》中的计算几何部分，黄亮举了一个经典的例子，我认为很适合用来介绍离散化思想。这个问题是UVA10173(http://acm.uva.es/p/v101/10173.html)，题目意思很简单，给定平面上n个点的坐标，求能够覆盖所有这些点的最小矩形面积。这个问题难就难在，这个矩形可以倾斜放置（边不必平行于坐标轴）。

    这里的倾斜放置很不好处理，因为我们不知道这个矩形最终会倾斜多少度。假设我们知道这个矩形的倾角是α，那么答案就很简单了：矩形面积最小时四条边一定都挨着某个点。也就是说，四条边的斜率已经都知道了的话，只需要让这些边从外面不断逼近这个点集直到碰到了某个点。你不必知道这个具体应该怎么实现，只需要理解这可以通过某种方法计算出来，毕竟我们的重点在下面的过程。
    我们的算法很显然了：枚举矩形的倾角，对于每一个倾角，我们都能计算出最小的矩形面积，最后取一个最小值。
    这个算法是否是正确的呢？我们不能说它是否正确，因为它根本不可能实现。矩形的倾角是一个实数，它有无数种可能，你永远不可能枚举每一种情况。我们说，矩形的倾角是一个“连续的”变量，它是我们无法枚举这个倾角的根本原因。我们需要一种方法，把这个“连续的”变量变成一个一个的值，变成一个“离散的”变量。这个过程也就是所谓的离散化。
    我们可以证明，最小面积的矩形不但要求四条边上都有一个点，而且还要求至少一条边上有两个或两个以上的点。试想，如果每条边上都只有一个点，则我们总可以把这个矩形旋转一点使得这个矩形变“松”，从而有余地得到更小的矩形。于是我们发现，矩形的某条边的斜率必然与某两点的连线相同。如果我们计算出了所有过两点的直线的倾角，那么α的取值只有可能是这些倾角或它减去90度后的角（直线按“”方向倾斜时）这么C(n,2)种。我们说，这个“倾角”已经被我们 “离散化”了。虽然这个算法仍然有优化的余地，但此时我们已经达到了本文开头所说的目的。

    对于某些坐标虽然已经是整数（已经是离散的了）但范围极大的问题，我们也可以用离散化的思想缩小这个规模。最近搞模拟赛Vijos似乎火了一把，我就拿两道Vijos的题开刀。
    VOJ1056(http://www.vijos.cn/Problem_Show.asp?id=1056) 永远是离散化的经典问题。大意是给定平面上的n个矩形（坐标为整数，矩形与矩形之间可能有重叠的部分），求其覆盖的总面积。平常的想法就是开一个与二维坐标规模相当的二维Boolean数组模拟矩形的“覆盖”（把矩形所在的位置填上True）。可惜这个想法在这里有些问题，因为这个题目中坐标范围相当大（坐标范围为-10^8到10^8之间的整数）。但我们发现，矩形的数量n<=100远远小于坐标范围。每个矩形会在横纵坐标上各“使用”两个值， 100个矩形的坐标也不过用了-10^8到10^8之间的200个值。也就是说，实际有用的值其实只有这么几个。这些值将作为新的坐标值重新划分整个平面，省去中间的若干坐标值没有影响。我们可以将坐标范围“离散化”到1到200之间的数，于是一个200*200的二维数组就足够了。实现方法正如本文开头所说的“排序后处理”。对横坐标（或纵坐标）进行一次排序并映射为1到2n的整数，同时记录新坐标的每两个相邻坐标之间在离散化前实际的距离是多少。这道题同样有优化的余地。
    最后简单讲一下计算几何以外的一个运用实例（实质仍然是坐标的离散）。才考的VOJ1238(http://www.vijos.cn/Problem_Show.asp?id=1238)中，标程开了一个与时间范围一样大的数组来储存时间段的位置。这种方法在空间上来看十分危险。一旦时间取值范围再大一点，盲目的空间开销将导致Memory Limit Exceeded。我们完全可以采用离散化避免这种情况。我们对所有给出的时间坐标进行一次排序，然后同样用时间段的开始点和结束点来计算每个时刻的游戏数，只是一次性加的经验值数将乘以排序后这两个相邻时间点的实际差。这样，一个1..n的数组就足够了。

离散化的应用相当广泛，以后你会看到还有很多其它的用途。

2007.04.05补充：
VOJ1056那个例子看来还是有人不明白。
我发一张示意图，注意左边的10*7的数组是如何等价地转化为右边两个4*4的数组的

Matrix67原创
转载请注明出处

二分图最大匹配问题匈牙利算法

2005 年 9 月 27 日 / 37 条评论

研究了几个小时，终于明白了。说穿了，就是你从二分图中找出一条路径来，让路径的起点和终点都是还没有匹配过的点，并且路径经过的连线是一条没被匹配、一条已经匹配过，再下一条又没匹配这样交替地出现。找到这样的路径后，显然路径里没被匹配的连线比已经匹配了的连线多一条，于是修改匹配图，把路径里所有匹配过的连线去掉匹配关系，把没有匹配的连线变成匹配的，这样匹配数就比原来多1个。不断执行上述操作，直到找不到这样的路径为止。