1、1D/1D動態規劃優化初步 所謂1D/1D動態規劃，指的是狀態數為O(n)，每一個狀態決策量為O(n)的動態規劃方程。直接求解的時間復雜度為O(n2)，但是，絕大多數這樣的方程通過合理的組織與優化都是可以優化到O(nlogn)乃至O(n)的時間復雜度的。這里就想講一講我對一些比較初步的經典的優化方法的認識。 本文中不想進行過多的證明與推導，主要想說明經典模型的建立、轉化與求解方法。 由于本人認識與水平相當有限，如果出現什么錯誤與疏漏，還請大牛多多指正。另外，也希望大牛們更多地向我們介紹一下有關動態規劃優化的更深入的東西。 本文中使用兩種方式表示一個函數：f(x)與fx，用方括號表示的函數值可以

2、在規劃之前全部算出（常量），而用圓括號表示的函數值必須在規劃過程中計算得到（變量）。無論是什么函數值一經確定，在以后的計算中就不會更改。經典模型一： 相信這個方程大家一定是不陌生的。另外，肯定也知道一個關于決策單調性的性質： 假如用k(x)表示狀態x取到最優值時的決策，則決策單調性表述為： ，當且僅當： ，對于這個性質的證明讀者可以在任意一篇講述四邊形不等式的文章中找到，所以這里不再重復。而且，從實戰的角度來看，我們甚至都不需要驗證w函數的這個性質，最經濟也是最可靠的方法是寫一個樸素算法打出決策表來觀察（反正你總還是要對拍）。當然，有的時候題目要求你做一點準備工作，去掉一些明顯不可能的決策，然

3、后在應用決策單調性。這是上述性質也許會有點用處。 正如前文中所述，我們關注的重點是怎樣實現決策單調性。有了決策單調性，怎樣高效地實現它呢？很容易想到在枚舉決策的時候，不需要從1開始，只要從k(x-1)開始就可以了，但這只能降低常數，不可能起到實質性的優化。 另一種想法是從k(x-1)開始枚舉決策更新f(x)，一旦發現決策u不如決策u+1來得好，就停止決策過程，選取決策u作為f(x)的最終決策。這樣時間是很大提高了，但可惜是不正確的。決策單調性并沒有保證f(j)+wj,x有什么好的性質，所以這樣做肯定是不對的。 剛才我們總是沿著“f(x)的最優決策是什么”這個思路進行思考，下面我們換一個角度，思

4、考對于一個已經計算出來的狀態f(j)，“f(j)能夠更新的狀態有哪些”。這樣，每一步過程中某些狀態的決策可能不是最優的，但是當算法結束的時候所有狀態對應的決策一定是最優的。 一開始，只有f(1)的函數值被計算出來，于是所有狀態的當前最優決策都是1。 現在，顯然f(2)的值已經確定了：它的最有決策只能是1。我們用決策2來更新這個決策表。由于決策單調性，我們知道新的決策表只能有這樣的形式： 222222222222222222222222222222 這意味著我們可以使用二分法來查找“轉折點”，因為如果在一個點x上，如果決策2更好，則所有比x大的狀態都是決策2更好；如果x上決策1更好，則所有比x小

5、的狀態都是決策1更好。 現在決策1和決策2都已經更新完畢，則f(3)業已確定，現在用決策3來更新所有狀態。根據決策單調性，現在的決策表只能有以下2種類型： 22222222222222222233333333333 333333333333333333333333333333333333 而這樣的決策表示絕對不會出現的： 333333333333333333322222222222222222222222222222，不可能。 那么，我們的更新算法就是：考察決策2的區間b,e的b點上是否決策3更優，如果是，則全部拋棄決策2，將此區間劃歸決策3；如果否，則在決策2的區間b,e中二分查找轉折點。如

6、果第1問的回答是“是”，則用同樣的方法考察決策1。 推演到這一步，相信決策單調性的實現算法已經明了了：使用一個棧來維護數據，占中的每一個元素保存一個決策的起始位置與終了位置，顯然這些位置相互連接且依次遞增。當插入一個新的決策時，從后到前掃描棧，對于每一個老決策來說，做這樣兩件事：如果在老決策的起點處還是新決策更好，則退棧，全額拋棄老決策，將其區間合并至新決策中，繼續掃描下一個決策。如果在老決策的起點處是老決策好，則轉折點必然在這個老決策的區間中；二分查找之，然后新決策進棧，結束。由于一個決策出棧之后再也不會進入，所以均攤時間為O(1)，但是由于二分查找的存在，所以整個算法的時間復雜度為O(nl

7、ogn)。下面我們來看兩個例題。例題1：玩具裝箱。題目來源：湖南省選2008。題目大意：有n個玩具需要裝箱，每個玩具的長度為ci，規定在裝箱的時候，必須嚴格按照給出的順序進行，并且同一個箱子中任意兩個玩具之間必須且只能間隔一個單位長度，換句話說，如果要在一個箱子中裝編號為ij的玩具，則箱子的長度必須且只能是 ，規定每一個長度為l的箱子的費用是，其中L是給定的一個常數。現在要求你使用最少的代價將所有玩具裝箱，箱子的個數無關緊要。分析：本題可以很輕松地列出一個1D1D的動態規劃方程： ，其中。 不難驗證這個方程式滿足決策單調性的，于是我們可以直接套用上文中的方法進行優化，時間復雜度為O(nlogn

8、)。例題2：土地購買題目來源：USACO Monthly, March, 2008, Gold題目大意：有N塊土地需要購買，每塊土地都是長方形的，有特定的長與寬。你可以一次性購買一組土地，價格是這組土地中長的最大值乘以寬的最大值。比方說一塊5*3的土地和一塊2*9的土地在一起購買的價格就是9*3。顯然，怎樣分組購買土地是一門學問，你的任務就是設計一種方案用最少的錢買下所有的土地。分析：將所有土地按照長度降序排列，依次檢索，則當前土地的長度必然在上一塊土地之內，我們只需要考慮寬度就可以了。而在寬度的問題上，當前土地的行為只能是這樣：和前面若干塊土地綁定；同時這些綁定的土地和他們前后的土地分離。這

9、樣很容易得出狀態轉移方程：這個方程還不能滿足決策單調性，下面我們試圖再做一下簡化。如果將每一個土地的尺寸看成是一個二維坐標的話，（如下圖） 其中不難看出，紅色點完全可以忽略，這些點(x,y)必然滿足一個性質：存在點(x, y)同時滿足x = x且y = y，這樣它就能被一個組完全覆蓋。這些被忽略的點可以通過一次線形的掃描得出。 下面，我們著重來看一下不能被忽略的這些點，它們的排布方式必然是單調減。因此狀態轉移方程可以寫成這個樣子： 這個轉移方程就是標準的決策單調性了，讀者可以通過w函數的性質直接證明它。然后，就用上文中的方法在O(nlogn)時間內求解。 以上兩個例子都是決策單調性的直接應用。

10、其中第二個例子稍微復雜一些，如果不忽略那些“肯定無用”的決策，不對數據進行有序化，則方程是不滿足決策單調性的。這也就提醒我們在做這一類題目的時候不能鉆牛角尖死做，還得靈活一點。 另外，決策單調性提供的只是O(nlogn)的算法，事實上上面兩個例題的最佳算法都是O(n)的，在后文中我們將詳細介紹另外一種經典模型，并且試圖將這兩個規劃方程通過數學變換轉向另一個模型。=下面我們來看一類特殊的w函數：，顯然，這一類函數都是滿足決策單調性的。但是不同的是，由于這一類函數的特殊性，他們可以用一種更加簡潔也更加有借鑒意義的方法解決。 由于w函數滿足，我們總是可以找到一個特定的一元函數wx，使得，這樣，假設狀

11、態f(x)的某一個決策是k，有：，其中。這樣我們發現：一旦f(k)被確定，相應地g(k)也被確定，更加關鍵的是，無論k值如何，wx-w1總是一個常數。換句話說，我們可以把方程寫成下述形式：。不難發現這個方程是無聊的，因為我們可以用一個變量“打擂臺”直接存儲；但是，如果在k的下界上加上一個限制，那這個方程就不是很無聊了。于是，我們就得到了另一個經典模型。經典模型二：，其中，bx隨x不降。 這個方程怎樣求解呢？我們注意到這樣一個性質：如果存在兩個數j, k，使得j = k，而且g(k) = g(j)，則決策j是毫無用處的。因為根據bx單調的特性，如果j可以作為合法決策，那么k一定可以作為合法決策，

12、又因為k比j要優，（注意：在這個經典模型中，“優”是絕對的，是與當前正在計算的狀態無關的），所以說，如果把待決策表中的決策按照k排序的話，則g(k)必然是不降的。 這樣，就引導我們使用一個單調隊列來維護決策表。對于每一個狀態f(x)來說，計算過程分為以下幾步：隊首元素出隊，直到隊首元素在給定的范圍中。此時，隊首元素就是狀態f(x)的最優決策，計算g(x)，并將其插入到單調隊列的尾部，同時維持隊列的單調性（不斷地出隊，直到隊列單調為止）。重復上述步驟直到所有的函數值均被計算出來。不難看出這樣的算法均攤時間復雜度是O(1)的。下面我們來看幾個例題。例題3：The Sound of Silence題

13、目來源：Baltic Olympiad in Informatics 2007題目大意：給出一個N項的數列，如果對于一個連續的長度為M的片段來說，片段內所有數中最大值與最小值的差不超過一個給定的常數C，則我們稱這樣的片段是一個合法的片段。編程求出所有的合法片段的起始位置。分析：本題不難看出可以分解為兩個子問題：求所有片段的最大值以及求所有片段的最小值。而這兩個任務實際上是一樣的，所以我們只需要求取所有的連續M個數的片段中的最小值。 這個任務有很多很多種對數級算法，其中用堆或者用靜態最優二叉樹都可以做到O(nlogm)，但是這題的O(n)算法還是不那么好想的。 事實上，如果用gx表示數列中第x個

14、數的值，用f(x)表示以x作為結尾的有M個數的連續片段的話，顯然有： ，直接吻合經典模型二。套用算法，就可以在O(n)的時間內解決問題。 （當然，本題還有一種別致的“窗口”算法，也漂亮地在O(n)的時間內解決了問題，詳細可以看官方的解題報告。這里引入本題的主要目的是在于佐證上文中討論到的經典模型二）例題4：Islands題目來源：IOI2008題目大意：給出一個具有N個頂點的無向加權圖，同時這個圖中有且恰有N條邊。現在，對于這個圖中的每一個連通分量，求出其最長路徑（權值和最大，一個節點在路徑上最多只能出現一次）。分析：當然，這個問題更多的是一個圖論題。但是在最后關鍵問題的處理上還是可以看到經典

15、模型二的影子。 首先，用BFS找出所有連通分量。然后，對于一個連通分量來說，由于點數與邊數相同，因此必然構成基環+外向樹的結構。我們可以找出基環并確定所有外向樹的結構。一條最長路徑有兩種可能：完整地位于某一棵外向樹中；或者位于兩棵外向樹中，其間通過基環的一段連接。第一種可能可以通過樹形DP解決，問題就在于第二種可能怎樣處理。如果枚舉兩棵外向樹，那就是O(n2)，就不可以接受了。 我們考慮破環為鏈，然后將鏈整體左移，制作一個副本。比方說，如果原來的環是：14 2，以1為首破環，得：1-2-3-4，然后制作副本，得2-3-4-1-2-3-4，制作副本3的主要目的是使得對于每一個點的方程都有統一的形

16、式，使得環上所有片段都可以對應鏈上的一個片段。這種情況下，用gx表示x點上外向樹上的最長下降路的長度，f(x)表示以該點為終點的總最長路徑的長度，則有：，其中w函數即顯然滿足，通過變換之后就可以變成經典模型二。這樣，就在總O(n)的時間內解決了本題。 如果還嫌以上兩個問題不夠典型，下面舉一個典型到所有OIer都耳熟能詳的題目。例題5：有限背包問題。題目來源：經典問題。題目大意：有N件物品，每一件物品的價值為pk，重量為wk，最多只能選取mk次；現在給出背包的最大承重量C，要求在滿足重量要求的條件下使得背包中的物品價值總和最大。分析：如果mk = 1或者mk = +，就都很好做。但現在mk是一個

17、有界值，就比較麻煩了。我們還是按照背包問題的常見思路，一次枚舉每一個物品。設當前枚舉的物品編號為k，用f(x)表示：為了到達價值x，背包的重量至少應該是多少；則我們有：，這個方程很麻煩，因為某一個狀態的決策不是連續的，而是間斷性的。怎樣把決策區間變成一段連續區間呢？很容易想到等價類的思想；如果按照模pk對所有的f(x)劃分等價類，那么在同一個等價類中，決策區間就是連續的了，我們不妨把新函數設為h(x)，則方程變為：，其中，w函數即顯然滿足，（注意wk是一個與i和j無關的常量）經過適當的變化后可以轉化為經典模型二。于是有限背包問題可以在O(NP)的時間內解決，其中P是背包可能取到的最大價值。（其

18、實換成重量也一樣），這也就是“背包十講”中所說的那個單調隊列法。 我們注意到，如果mk=1的話，那么每一個f(x)的決策量都是O(1)，這沒什么問題；但如果mk = +，有意味著什么呢？仔細觀察可以發現，這實際上就拿掉了方程中的循環變量的下界，對應的是這樣的一個方程，這顯然是很簡單的，適用單變量打擂臺就可以解決了（盡管我們通常并不這樣做）。所以說，借助經典模型二，我們在一個更高的高度上統一了0-1、有限、無限三大背包問題。下面我們再次來看一下例題2土地購買中的那個方程：，我們來仔細地觀察這個方程：f(k)是變量，yk+1是常量，但不論怎么說，這兩個量在以后的計算中都不會變化。而xn是一個比例系

19、數，它與k無關，只隨著x的變化而變化。如果我們建立平面直角坐標系，以f(k)作為橫軸，yk+1作為縱軸，則每一個狀態f(k)都可以看作是該坐標系中的一個點。在求解狀態f(n)的過程中，我要求最小化：，其中x, y是我建立的直角坐標系中某一個點的坐標（表示一個決策），k就是方程中的xn，是只與n有關，而與決策無關的一個常量。這個最小化問題是什么呢？其實就是一個平面上的線性規劃。我們把式子改寫成：，就演變成了這樣的一個問題：在一個直線簇中，選取一條直線，使得這條直線過某個給出的數據點，同時C要最小。既然問題變成了這么有意思的線性規劃問題，就有必要進一步的研究，看看是不時有更好的解法，這就導致了我們

20、的另一個經典模型：經典模型三：。 注意：這個模型寫的比較抽象，其實它的涵蓋范圍是很廣的。首先，ax, bx不一定要是常量，只要他們與決策無關，都可以接受；另外，f(i)和g(i)不管是常量還是變量都沒有關系，只要他們是一個有最優的f(x)決定的二元組就可以了。 因此，為了方便描述，我們把這個模型寫成下面這個形式：， 其中，x(i)，y(i)都是可以在常數時間內通過f(i)唯一決定的二元組。 這個經典模型怎樣轉化求解呢？前文說過，這樣的模型的求解與平面上的線性規劃有關，我們以x(i)為橫軸，y(i)為縱軸建立平面直角坐標系，這樣一個狀態f(i)所決定的二元組就可以用坐標系中的一個點表示。然后，我

21、們的目標是： ，其中，化成：，假設（反之亦然），則我們的任務是使得這條直線的縱截距最小。可以想象有一組斜率相同的直線自負無窮向上平移，所碰到的第一個數據點就是最優決策。 這個時候，有一個重要的性質，那就是：所有最優決策點都在平面點集的凸包上。基于這個事實，我們可以開發出很多令人滿意的算法。 這時，根據直線斜率與數據點分布的特征，可以劃分為兩種情況：情況一：決策直線的斜率與二元組的橫坐標同時滿足單調性。（具體的單調性視最優化目標的性質而定） 這樣的模型是比較好處理的，因為這個時候由于斜率變化是單調的，所以決策點必然在凸殼上單調移動。我們只需要維護一個單調隊列和一個決策指針，每次決策時作這樣幾件事

22、：決策指針（也就是隊首）后移，直至最佳決策點。進行決策。將進行決策之后的新狀態的二元組加入隊尾，同時作Graham-Scan式的更新操作維護凸殼。（注意此時當前指針所在二元組有可能被拋棄）算法的時間復雜度為O(n)情況二：沒有任何限制。 這時問題的解決就比較困難了。顯然，決策點還是應該在凸殼上。我們不妨考慮一個單調減的凸殼，這個凸殼上點與點之間的連線必然滿足這樣的性質：斜率單調減。通過細致的觀察我們可以發現，對于一個給定的斜率k來說，對應的直線簇中具有最大縱截距的直線通過的決策點必然滿足這樣的性質：該點兩側的邊的斜率k1, k2滿足。 這樣，我們就可以通過二分查找來確定最佳的決策點。 但是，在

23、插入數據點的過程中，我們遇到的麻煩可能更大。首先，肯定是二分查找確定橫坐標的插入點，然后對兩側分別進行Graham維護凸性。但接下來的問題就嚴重了：在維護凸形的過程中我們肯定刪掉了一些點，怎樣重新得到一個完整的凸殼決策表呢？使用move是一個折中的辦法，但是這與理論的時間復雜度分析根本無益。 完美的解決方法是應用平衡二叉樹。我們以橫坐標為關鍵字建立平衡二叉樹，這樣查找和插入的過程都可以在O(logn)時間內完成。當我們做Graham維護時，首先將新數據點Splay到根節點，此時剩下的節點必然分居左子樹和右子樹。然后，我們以左子樹為例，后序遍歷依次查找節點，直至查找到一個滿足凸形的節點。將這個節

24、點Splay到根節點的左孩子，然后刪掉這個節點的右孩子。這樣的算法的時間復雜度是O(nlogn)，但是實現起來非常復雜。 下面我們來看幾個例題。例題6：玩具裝箱的線性算法。 例題1中玩具裝箱的動態規劃方程為： ，下面，我們試圖通過數學變換將其變成經典模型三。 為了簡化計算，設，則： ， 不妨設，顯然這兩個量都是常量，則： ，然后問題就明朗了，設平面直角坐標系中，則問題變成：，其對應的線性規劃的目標直線為。回顧定義不難看出，ax隨著x的增大而增大，x(i)也隨著i的增大而增大。因此，問題中直線斜率單調減，數據點橫坐標單調增，符合經典模型三種的情形1。使用單調隊列維護凸殼可以在O(n)的時間內解決

25、本題。例題七：貨幣兌換。題目來源：NOI2007題目大意：有3種貨幣體系：人民幣，A券，B券，其中A券與B券的價格在每一天都是不同的。在某一天D，你可以做3件事情：如果你的手頭上有A券或B券，你可以將它們都按照當天的價格換成人民幣。如果你的手頭上有人民幣，你可以將它們按照一個特定的比例Rate并以照當天的價格換成A券和B券（就是說你兌換的A券和B券的價值比是Rate）什么也不做。一開始你有一些人民幣，請你通過最佳的操作方式在最后一天結束的時候手頭上握有最多的人民幣。分析：試題中的Hint已經告訴我們，如果我們想買進人民幣，就必須全額買進；如果我們想賣出人民幣，就必須全額賣出。由于不管是在哪一天

26、，人民幣總是越多越好；我們用f(n)表示到了第n天最多可能持有的人民幣數量，用x(i)和y(i)表示在第i天，用最多的錢能夠換成的A券和B券。（注意：由于Rate確定，兌換金額確定，所以A券和B券的數量是唯一確定的），我們有：，其中an和bn代表A券和B券在第n天的牌價。 這個方程式符合經典模型三中的情形二。所以，我們應該使用一個平衡樹來維護凸形。時間復雜度是O(nlogn)。由于數據弱，所以這道題目用move也是可以搞定的。 這篇文章中，我們著重討論了這樣三類經典模型的建立與求解過程：經典模型一：，wi, x滿足決策單調性。經典模型二：，其中bx單調增。經典模型三：，其中x(i)，y(i)可以由f(i)在常數時間內唯一確定。 這三類模型都可以在至少O(nlogn)的時間內解決，從而起到了對1D/1D的方程的優化作用。另外，這三種模型并不是孤立存在的，而是可以互相轉化的，文中的很多例題就兼具多種模型的特點。 當然，本文只是對1D/1D動態規劃優化的很初步很淺顯的探討，還有一些問題值得深入研究：在經典模型一中，是否存在對于任意滿足決策單調性的w函數都適用的O(n)的算法？我們只給出了O(nlogn)的通用算法以及對于一些特殊w函數的O(n)算法，希望能夠獲得通用的簡潔的O(n)算法。在經典模型一和經典模型二中，我們都可以給決策范圍加上一個下界bx而絲毫不影響時間效