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