D1D動(dòng)態(tài)規(guī)劃優(yōu)化初步

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

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

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

4、考對(duì)于一個(gè)已經(jīng)計(jì)算出來(lái)的狀態(tài)f(j)，“f(j)能夠更新的狀態(tài)有哪些”。這樣，每一步過(guò)程中某些狀態(tài)的決策可能不是最優(yōu)的，但是當(dāng)算法結(jié)束的時(shí)候所有狀態(tài)對(duì)應(yīng)的決策一定是最優(yōu)的。 一開(kāi)始，只有f(1)的函數(shù)值被計(jì)算出來(lái)，于是所有狀態(tài)的當(dāng)前最優(yōu)決策都是1。 現(xiàn)在，顯然f(2)的值已經(jīng)確定了：它的最有決策只能是1。我們用決策2來(lái)更新這個(gè)決策表。由于決策單調(diào)性，我們知道新的決策表只能有這樣的形式： 222222222222222222222222222222 這意味著我們可以使用二分法來(lái)查找“轉(zhuǎn)折點(diǎn)”，因?yàn)槿绻谝粋€(gè)點(diǎn)x上，如果決策2更好，則所有比x大的狀態(tài)都是決策2更好；如果x上決策1更好，則所有比x小

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

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

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

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

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

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

11、態(tài)f(x)的某一個(gè)決策是k，有：，其中。這樣我們發(fā)現(xiàn)：一旦f(k)被確定，相應(yīng)地g(k)也被確定，更加關(guān)鍵的是，無(wú)論k值如何，wx-w1總是一個(gè)常數(shù)。換句話說(shuō)，我們可以把方程寫(xiě)成下述形式：。不難發(fā)現(xiàn)這個(gè)方程是無(wú)聊的，因?yàn)槲覀兛梢杂靡粋€(gè)變量“打擂臺(tái)”直接存儲(chǔ)；但是，如果在k的下界上加上一個(gè)限制，那這個(gè)方程就不是很無(wú)聊了。于是，我們就得到了另一個(gè)經(jīng)典模型。經(jīng)典模型二：，其中，bx隨x不降。 這個(gè)方程怎樣求解呢？我們注意到這樣一個(gè)性質(zhì)：如果存在兩個(gè)數(shù)j, k，使得j = k，而且g(k) = g(j)，則決策j是毫無(wú)用處的。因?yàn)楦鶕?jù)bx單調(diào)的特性，如果j可以作為合法決策，那么k一定可以作為合法決策，

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

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

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

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

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

17、有界值，就比較麻煩了。我們還是按照背包問(wèn)題的常見(jiàn)思路，一次枚舉每一個(gè)物品。設(shè)當(dāng)前枚舉的物品編號(hào)為k，用f(x)表示：為了到達(dá)價(jià)值x，背包的重量至少應(yīng)該是多少；則我們有：，這個(gè)方程很麻煩，因?yàn)槟骋粋€(gè)狀態(tài)的決策不是連續(xù)的，而是間斷性的。怎樣把決策區(qū)間變成一段連續(xù)區(qū)間呢？很容易想到等價(jià)類(lèi)的思想；如果按照模pk對(duì)所有的f(x)劃分等價(jià)類(lèi)，那么在同一個(gè)等價(jià)類(lèi)中，決策區(qū)間就是連續(xù)的了，我們不妨把新函數(shù)設(shè)為h(x)，則方程變?yōu)椋海渲?，w函數(shù)即顯然滿足，（注意wk是一個(gè)與i和j無(wú)關(guān)的常量）經(jīng)過(guò)適當(dāng)?shù)淖兓罂梢赞D(zhuǎn)化為經(jīng)典模型二。于是有限背包問(wèn)題可以在O(NP)的時(shí)間內(nèi)解決，其中P是背包可能取到的最大價(jià)值。（其

18、實(shí)換成重量也一樣），這也就是“背包十講”中所說(shuō)的那個(gè)單調(diào)隊(duì)列法。 我們注意到，如果mk=1的話，那么每一個(gè)f(x)的決策量都是O(1)，這沒(méi)什么問(wèn)題；但如果mk = +，有意味著什么呢？仔細(xì)觀察可以發(fā)現(xiàn)，這實(shí)際上就拿掉了方程中的循環(huán)變量的下界，對(duì)應(yīng)的是這樣的一個(gè)方程，這顯然是很簡(jiǎn)單的，適用單變量打擂臺(tái)就可以解決了（盡管我們通常并不這樣做）。所以說(shuō)，借助經(jīng)典模型二，我們?cè)谝粋€(gè)更高的高度上統(tǒng)一了0-1、有限、無(wú)限三大背包問(wèn)題。下面我們?cè)俅蝸?lái)看一下例題2土地購(gòu)買(mǎi)中的那個(gè)方程：，我們來(lái)仔細(xì)地觀察這個(gè)方程：f(k)是變量，yk+1是常量，但不論怎么說(shuō)，這兩個(gè)量在以后的計(jì)算中都不會(huì)變化。而xn是一個(gè)比例系

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

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

21、們的目標(biāo)是： ，其中，化成：，假設(shè)（反之亦然），則我們的任務(wù)是使得這條直線的縱截距最小?？梢韵胂笥幸唤M斜率相同的直線自負(fù)無(wú)窮向上平移，所碰到的第一個(gè)數(shù)據(jù)點(diǎn)就是最優(yōu)決策。 這個(gè)時(shí)候，有一個(gè)重要的性質(zhì)，那就是：所有最優(yōu)決策點(diǎn)都在平面點(diǎn)集的凸包上?；谶@個(gè)事實(shí)，我們可以開(kāi)發(fā)出很多令人滿意的算法。 這時(shí)，根據(jù)直線斜率與數(shù)據(jù)點(diǎn)分布的特征，可以劃分為兩種情況：情況一：決策直線的斜率與二元組的橫坐標(biāo)同時(shí)滿足單調(diào)性。（具體的單調(diào)性視最優(yōu)化目標(biāo)的性質(zhì)而定） 這樣的模型是比較好處理的，因?yàn)檫@個(gè)時(shí)候由于斜率變化是單調(diào)的，所以決策點(diǎn)必然在凸殼上單調(diào)移動(dòng)。我們只需要維護(hù)一個(gè)單調(diào)隊(duì)列和一個(gè)決策指針，每次決策時(shí)作這樣幾件事

22、：決策指針（也就是隊(duì)首）后移，直至最佳決策點(diǎn)。進(jìn)行決策。將進(jìn)行決策之后的新?tīng)顟B(tài)的二元組加入隊(duì)尾，同時(shí)作Graham-Scan式的更新操作維護(hù)凸殼。（注意此時(shí)當(dāng)前指針?biāo)诙M有可能被拋棄）算法的時(shí)間復(fù)雜度為O(n)情況二：沒(méi)有任何限制。 這時(shí)問(wèn)題的解決就比較困難了。顯然，決策點(diǎn)還是應(yīng)該在凸殼上。我們不妨考慮一個(gè)單調(diào)減的凸殼，這個(gè)凸殼上點(diǎn)與點(diǎn)之間的連線必然滿足這樣的性質(zhì)：斜率單調(diào)減。通過(guò)細(xì)致的觀察我們可以發(fā)現(xiàn)，對(duì)于一個(gè)給定的斜率k來(lái)說(shuō)，對(duì)應(yīng)的直線簇中具有最大縱截距的直線通過(guò)的決策點(diǎn)必然滿足這樣的性質(zhì)：該點(diǎn)兩側(cè)的邊的斜率k1, k2滿足。 這樣，我們就可以通過(guò)二分查找來(lái)確定最佳的決策點(diǎn)。 但是，在

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

24、點(diǎn)Splay到根節(jié)點(diǎn)的左孩子，然后刪掉這個(gè)節(jié)點(diǎn)的右孩子。這樣的算法的時(shí)間復(fù)雜度是O(nlogn)，但是實(shí)現(xiàn)起來(lái)非常復(fù)雜。 下面我們來(lái)看幾個(gè)例題。例題6：玩具裝箱的線性算法。 例題1中玩具裝箱的動(dòng)態(tài)規(guī)劃方程為： ，下面，我們?cè)噲D通過(guò)數(shù)學(xué)變換將其變成經(jīng)典模型三。 為了簡(jiǎn)化計(jì)算，設(shè)，則： ， 不妨設(shè)，顯然這兩個(gè)量都是常量，則： ，然后問(wèn)題就明朗了，設(shè)平面直角坐標(biāo)系中，則問(wèn)題變成：，其對(duì)應(yīng)的線性規(guī)劃的目標(biāo)直線為?；仡櫠x不難看出，ax隨著x的增大而增大，x(i)也隨著i的增大而增大。因此，問(wèn)題中直線斜率單調(diào)減，數(shù)據(jù)點(diǎn)橫坐標(biāo)單調(diào)增，符合經(jīng)典模型三種的情形1。使用單調(diào)隊(duì)列維護(hù)凸殼可以在O(n)的時(shí)間內(nèi)解決

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

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