Posted on 2008-08-20 21:31
Hero 閱讀(356)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
資料整理
1 一個(gè)著名的定理是這樣的：最長(zhǎng)上升序列的長(zhǎng)度等于不上升序列的最小分劃（即將平面上的點(diǎn)分劃成盡可能少的不相交的不上升序列）。下面我們就來(lái)給出這個(gè)定理的證明，在證明的過(guò)程中，我們甚至可以得到求具體分割方案的方法。
2 證明：
3 一個(gè)顯然的結(jié)論是最長(zhǎng)上升序列的長(zhǎng)度小于等于不上升序列的最小分劃。因?yàn)樯仙蛄兄腥我鈨牲c(diǎn)都不可能屬于同一個(gè)不上升序列。也就是說(shuō)，最長(zhǎng)上升序列中的所有點(diǎn)分屬不同的不上升序列。所以，不上升序列的分劃數(shù)最少也不會(huì)少于最長(zhǎng)上升序列的長(zhǎng)度。
4 關(guān)鍵的是要證明，最長(zhǎng)上升序列的長(zhǎng)度大于等于不上升序列的最小分劃。我們來(lái)構(gòu)造一個(gè)不上升序列的分劃。
5 首先在二維Euclid空間中取出所有的滿足如下性質(zhì)的點(diǎn)(x, y)：對(duì)于任意的點(diǎn)(x'', y'')，總滿足x''≤x || y''≤y，即(x，y)的“右上方”沒(méi)有別的點(diǎn)。可以證明，取出的點(diǎn)集{(x，y)}是一條不上升序列。因?yàn)辄c(diǎn)集中任意兩點(diǎn)(x1, y1)和(x2, y2)總滿足x1≤x2 || y1≤y2且x2≤x1 || y2≤y1，整理一下即得(x1≤x2)xor(y1≤y2)＝true。所以，把這些點(diǎn)按x升序排列后，得到的y相應(yīng)的成降序。
6 將上面取出的點(diǎn)從空間中去除后，重復(fù)上述過(guò)程，又可以得到一條新的不上升序列。如此反復(fù)……可以得到一個(gè)不上升序列的分劃(現(xiàn)在還不能肯定這就是最小的分劃)。由前面的結(jié)論知道，這個(gè)分劃數(shù)必定大于等于最長(zhǎng)上升序列的長(zhǎng)度。
7 我們對(duì)得到的不上升序列分劃進(jìn)行分級(jí)，先取出的等級(jí)最高，最后取出的等級(jí)最低。這樣就得到k條分屬level1，level2，…，levelk的不上升序列。
8 這些鏈上的點(diǎn)滿足這樣的性質(zhì)：對(duì)于一個(gè)屬于leveli(i<k)鏈上的點(diǎn)(x, y)，必然存在一個(gè)屬于leveli+1的點(diǎn)(x'', y'')，使得x<x'' && y<y''。否則(x, y)在取leveli+l鏈時(shí)就會(huì)被取走，不應(yīng)屬于leveli。
9 從level1上的一點(diǎn)（x1, y1）開(kāi)始，取level2的點(diǎn)（x2, y2），x2>x1 && y2>y1，然后取level3的點(diǎn)（x3, y3）……最后必然能取到levelk上的點(diǎn)（xk, yk）。如此得到的序列（x1, y1），（x2, y2），…，（xk, yk），就是一條上升序列。所以，我們前面得到的不上升序列的分劃數(shù)就不可能大于最長(zhǎng)上升序列長(zhǎng)度。
10 這就證明了最長(zhǎng)上升序列的長(zhǎng)度大于等于不上升序列的最小分劃。再加上“最長(zhǎng)上升序列的長(zhǎng)度小于等于不上升序列的最小分劃”的結(jié)論，就證明了最長(zhǎng)上升序列的長(zhǎng)度等于不上升序列的最小分劃。
11 這個(gè)證明的優(yōu)點(diǎn)在于，它是一個(gè)構(gòu)造性的證明，并且揭示了最長(zhǎng)上升序列與不上升序列最小分劃之間的較為深刻的關(guān)系。
12 根據(jù)前面的證明，我們可以很容易得到兩種解決本題的方法：
13 （1）在給出的二元組中求出最長(zhǎng)下降序列的長(zhǎng)度（具體實(shí)現(xiàn)比較簡(jiǎn)單，這里就從略了）；
14 （2）用類似Topologic排序的方法，構(gòu)造性的求出不下降序列的最小分割(詳細(xì)過(guò)程見(jiàn)證明)。
15 這兩種方法的時(shí)間復(fù)雜度都是O(n2)的。實(shí)際上，本題還能優(yōu)化到O(nlog2n)級(jí)，考慮到題目的規(guī)模以及本文的側(cè)重點(diǎn)，這里就不詳細(xì)展開(kāi)了。此外，前面講的方法（2），也是求最長(zhǎng)雙鏈問(wèn)題的一個(gè)基礎(chǔ)。