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

1D/1D動態(tài)規(guī)劃優(yōu)化初步所謂1D/1D動態(tài)規(guī)劃，指的是狀態(tài)數(shù)為O(n),每一個狀態(tài)決策量為O(n)的動態(tài)規(guī)劃方程。直接求解的時間復雜度為O(n2),但是，絕大多數(shù)這樣的方程通過合理的組織與優(yōu)化都是可以優(yōu)化到O(nlogn)乃至O(n)的時間復雜度的。這里就想講一講我對一些比較初步的經(jīng)典的優(yōu)化方法的認識。本文中不想進行過多的證明與推導,主要想說明經(jīng)典模型的建立、轉(zhuǎn)化與求解方法。由于本人認識與水平相當有限,如果出現(xiàn)什么錯誤與疏漏,還請大牛多多指正。另外,也希望大牛們更多地向我們介紹一下有關(guān)動態(tài)規(guī)劃優(yōu)化的更深入的東西。本文中使用兩種方式表示一個函數(shù)：f(x)與f[x]，用方括號表示的函數(shù)值可以在規(guī)劃之前全部算出(常量),而用圓括號表示的函數(shù)值必須在規(guī)劃過程中計算得到(變量)。無論是什么函數(shù)值一經(jīng)確定，在以后的計算中就不會更改。經(jīng)典模型一： f(x)=min{f(i)+w[i,x]}i=1相信這個方程大家一定是不陌生的。另外，肯定也知道一個關(guān)于決策單調(diào)性的性質(zhì)：假如用k(X)表示狀態(tài)X取到最優(yōu)值時的決策，則決策單調(diào)性表述為：Vi<jki<kj)當且僅當：Vi<jwijl+w羊1,i1<W圧1,升]wi,j對于這個性質(zhì)的證明讀者可以在任意一篇講述四邊形不等式的文章中找到，所以這里不再重復。而且，從實戰(zhàn)的角度來看，我們甚至都不需要驗證w函數(shù)的這個性質(zhì)，最經(jīng)濟也是最可靠的方法是寫一個樸素算法打出決策表來觀察(反正你總還是要對拍)。當然，有的時候題目要求你做一點準備工作，去掉一些明顯不可能的決策，然后在應用決策單調(diào)性。這是上述性質(zhì)也許會有點用處。正如前文中所述，我們關(guān)注的重點是怎樣實現(xiàn)決策單調(diào)性。有了決策單調(diào)性，怎樣高效地實現(xiàn)它呢？很容易想到在枚舉決策的時候，不需要從1開始，只要從k(x-1)開始就可以了，但這只能降低常數(shù)，不可能起到實質(zhì)性的優(yōu)化。另一種想法是從k(x-1)開始枚舉決策更新f(x),—旦發(fā)現(xiàn)決策u不如決策u+1來得好，就停止決策過程，選取決策u作為f(x)的最終決策。這樣時間是很大提高了，但可惜是不正確的。決策單調(diào)性并沒有保證f(j)+w[j,x]有什么好的性質(zhì)，所以這樣做肯定是不對的。剛才我們總是沿著“f(x)的最優(yōu)決策是什么”這個思路進行思考，下面我們換一個角度，思考對于一個已經(jīng)計算出來的狀態(tài)f(j)，“f(j)能夠更新的狀態(tài)有哪些”。這樣，每一步過程中某些狀態(tài)的決策可能不是最優(yōu)的，但是當算法結(jié)束的時候所有狀態(tài)對應的決策一定是最優(yōu)的。一開始，只有f(1)的函數(shù)值被計算出來，于是所有狀態(tài)的當前最優(yōu)決策都是1。111111111111111111111111111111111111111111111111111111111111111現(xiàn)在，顯然f(2)的值已經(jīng)確定了：它的最有決策只能是1。我們用決策2來更新這個決策表。由于決策單調(diào)性，我們知道新的決策表只能有這樣的形式：1111111111111111111111111111222222222222222222222222222222這意味著我們可以使用二分法來查找“轉(zhuǎn)折點”因為如果在一個點X上，如果決策2更好，則所有比x大的狀態(tài)都是決策2更好；如果x上決策1更好，則所有比x小的狀態(tài)都是決策1更好?，F(xiàn)在決策1和決策2都已經(jīng)更新完畢，則f(3)業(yè)已確定，現(xiàn)在用決策3來更新所有狀態(tài)。根據(jù)決策單調(diào)性，現(xiàn)在的決策表只能有以下2種類型：1111111111111111111111111111112222222222222222223333333333311111111111111111111111333333333333333333333333333333333333而這樣的決策表示絕對不會出現(xiàn)的：11111111111333333333333333333322222222222222222222222222222，不可能。那么，我們的更新算法就是：1、 考察決策2的區(qū)間[b,e]的b點上是否決策3更優(yōu)，如果是，則全部拋棄決策2,將此區(qū)間劃歸決策3；如果否，則在決策2的區(qū)間[b,e]中二分查找轉(zhuǎn)折點。2、 如果第1問的回答是“是”，則用同樣的方法考察決策1。推演到這一步，相信決策單調(diào)性的實現(xiàn)算法已經(jīng)明了了：使用一個棧來維護數(shù)據(jù)，占中的每一個元素保存一個決策的起始位置與終了位置，顯然這些位置相互連接且依次遞增。當插入一個新的決策時，從后到前掃描棧，對于每一個老決策來說，做這樣兩件事：1、 如果在老決策的起點處還是新決策更好，則退棧，全額拋棄老決策，將其區(qū)間合并至新決策中，繼續(xù)掃描下一個決策。2、 如果在老決策的起點處是老決策好，則轉(zhuǎn)折點必然在這個老決策的區(qū)間中；二分查找之，然后新決策進棧，結(jié)束。由于一個決策出棧之后再也不會進入，所以均攤時間為0(1)，但是由于二分查找的存在，所以整個算法的時間復雜度為O(nlogn)。下面我們來看兩個例題。例題1：玩具裝箱。題目來源：湖南省選2008。題目大意：有n個玩具需要裝箱，每個玩具的長度為c[i]，規(guī)定在裝箱的時候，必須嚴格按照給出的順序進行，并且同一個箱子中任意兩個玩具之間必須且只能間隔一個單位長度，換句話說，如果要在一個箱子中裝編號為i~j的玩具，則箱子的長度必須且只能是1=j—i+工c[k]，規(guī)定每一個長度為l的箱子的費用是P-(l-L)2，其中L是給定的k=i一個常數(shù)。現(xiàn)在要求你使用最少的代價將所有玩具裝箱，箱子的個數(shù)無關(guān)緊要。分析：本題可以很輕松地列出一個1D1D的動態(tài)規(guī)劃方程：f(x)=min{i+)w+[ X其中w[i,j]=(j—i+2Lc[k]-L)2。ii k=i不難驗證這個方程式滿足決策單調(diào)性的，于是我們可以直接套用上文中的方法進行優(yōu)化，時間復雜度為O(nlogn)。例題2：土地購買題目來源：USACOMonthly,March,2008,Gold題目大意：有N塊土地需要購買，每塊土地都是長方形的，有特定的長與寬。你可以一次性購買一組土地，價格是這組土地中長的最大值乘以寬的最大值。比方說一塊5*3的土地和一塊2*9的土地在一起購買的價格就是9*3。顯然，怎樣分組購買土地是一門學問，你的任務就是設計一種方案用最少的錢買下所有的土地。分析：將所有土地按照長度降序排列，依次檢索，則當前土地的長度必然在上一塊土地之內(nèi)，我們只需要考慮寬度就可以了。而在寬度的問題上，當前土地的行為只能是這樣：和前面若干塊土地綁定；同時這些綁定的土地和他們前后的土地分離。這樣很容易得出狀態(tài)轉(zhuǎn)移方程：f(n)=miin{(maxw[i])*l[k+1]+f(k)}k=0i=k+1這個方程還不能滿足決策單調(diào)性，下面我們試圖再做一下簡化。如果將每一個土地的尺寸看成是一個二維坐標的話，(如下圖)其中不難看出，紅色點完全可以忽略，這些點(x,y)必然滿足一個性質(zhì)：存在點(x',y')同時滿足x'>=x且y'>=y,這樣它就能被一個組完全覆蓋。這些被忽略的點可以通過一次線形的掃描得出。下面，我們著重來看一下不能被忽略的這些點，它們的排布方式必然是單調(diào)減。因此狀態(tài)轉(zhuǎn)移方程可以寫成這個樣子：f(n)=mni1n{x[n]*y[k+1]+f(k)}k=0這個轉(zhuǎn)移方程就是標準的決策單調(diào)性了，讀者可以通過w函數(shù)的性質(zhì)直接證明它。然后，就用上文中的方法在O(nlogn)時間內(nèi)求解。以上兩個例子都是決策單調(diào)性的直接應用。其中第二個例子稍微復雜一些，如果不忽略那些“肯定無用”的決策，不對數(shù)據(jù)進行有序化，則方程是不滿足決策單調(diào)性的。這也就提醒我們在做這一類題目的時候不能鉆牛角尖死做，還得靈活一點。另外，決策單調(diào)性提供的只是O(nlogn)的算法，事實上上面兩個例題的最佳算法都是O(n)的，在后文中我們將詳細介紹另外一種經(jīng)典模型，并且試圖將這兩個規(guī)劃方程通過數(shù)學變換轉(zhuǎn)向另一個模型。下面我們來看一類特殊的w函數(shù)：Vi<j<k,w[i,j]+w[j,k]二w[i,k]，顯然，這一類函數(shù)都是滿足決策單調(diào)性的。但是不同的是，由于這一類函數(shù)的特殊性，他們可以用一種更加簡潔也更加有借鑒意義的方法解決。由于w函數(shù)滿足Vi<j<k,w[i,j]+w[j,k]二w[i,k]，我們總是可以找到一個特定的一元函數(shù)w'x],使得Vi<j,w[i,j]二w'[j]-w'[x]，這樣，假設狀態(tài)f(x)的某一個決策是k，有：其中g(shù)(k)二f(k)—w[1,k]。f(x)=f(k)+w[k,x]=f(k)+w'[x]-w'[k]=g(k)+w'[x]其中g(shù)(k)二f(k)—w[1,k]。這樣我們發(fā)現(xiàn)：一旦f(k)被確定，相應地g(k)也被確定，更加關(guān)鍵的是，無論k值如何，w'[x]-w'[1]總是一個常數(shù)。換句話說，我們可以把方程寫成下述形式：f(x)二miin{g(k)}+w[1,x]。不難發(fā)現(xiàn)這個方程是無聊的，因為m!n{g(k)}我們可以用一k=1 k=1個變量“打擂臺”直接存儲；但是，如果舐的下界上加上一個限制，那這個方程就不是很無聊了。于是，我們就得到了另一個經(jīng)典模型。經(jīng)典模型一:f(x)=rnin{g(k)}+w[x]，其中，b[x]隨X不降。k=b[x]這個方程怎樣求解呢？我們注意到這樣一個性質(zhì)：如果存在兩個數(shù)j,k，使得j<=k，而且g(k)<=g(j)，則決策j是毫無用處的。因為根據(jù)b[x]單調(diào)的特性，如果j可以作為合法決策，那么k一定可以作為合法決策，又因為k比j要優(yōu)，(注意：在這個經(jīng)典模型中，“優(yōu)”是絕對的，是與當前正在計算的狀態(tài)無關(guān)的)，所以說，如果把待決策表中的決策按照k排序的話，則g(k)必然是不降的。這樣，就引導我們使用一個單調(diào)隊列來維護決策表。對于每一個狀態(tài)f(x)來說，計算過程分為以下幾步：1、 隊首元素出隊，直到隊首元素在給定的范圍中。2、 此時，隊首元素就是狀態(tài)f(x)的最優(yōu)決策，3、 計算g(x)，并將其插入到單調(diào)隊列的尾部，同時維持隊列的單調(diào)性(不斷地出隊，直到隊列單調(diào)為止)。重復上述步驟直到所有的函數(shù)值均被計算出來。不難看出這樣的算法均攤時間復雜度是0(1)的。下面我們來看幾個例題。例題3：TheSoundofSilence題目來源：BalticOlympiadinInformatics2007題目大意：給出一個N項的數(shù)列，如果對于一個連續(xù)的長度為M的片段來說，片段內(nèi)所有數(shù)中最大值與最小值的差不超過一個給定的常數(shù)C,則我們稱這樣的片段是一個合法的片段。編程求出所有的合法片段的起始位置。

分析：本題不難看出可以分解為兩個子問題：求所有片段的最大值以及求所有片段的最小值。而這兩個任務實際上是一樣的，所以我們只需要求取所有的連續(xù)M個數(shù)的片段中的最小值。這個任務有很多很多種對數(shù)級算法，其中用堆或者用靜態(tài)最優(yōu)二叉樹都可以做到O(nlogm)，但是這題的O(n)算法還是不那么好想的。事實上，如果用g[x]表示數(shù)列中第x個數(shù)的值，用f(x)表示以x作為結(jié)尾的有M個數(shù)的連續(xù)片段的話，顯然有：f(x)二mingi[，直接吻合經(jīng)典模型二。套用算法，就可以在O(n)的時間內(nèi)解決問題。i=x-ml-(當然，本題還有一種別致的“窗口”算法，也漂亮地在O(n)的時間內(nèi)解決了問題，詳細可以看官方的解題報告。這里引入本題的主要目的是在于佐證上文中討論到的經(jīng)典模型二)例題4：Islands題目來源：IOI2008題目大意：給出一個具有N個頂點的無向加權(quán)圖，同時這個圖中有且恰有N條邊。現(xiàn)在，對于這個圖中的每一個連通分量，求出其最長路徑(權(quán)值和最大，一個節(jié)點在路徑上最多只能出現(xiàn)一次)。分析：當然，這個問題更多的是一個圖論題。但是在最后關(guān)鍵問題的處理上還是可以看到經(jīng)典模型二的影子。首先，用BFS找出所有連通分量。然后，對于一個連通分量來說，由于點數(shù)與邊數(shù)相同,因此必然構(gòu)成基環(huán)+外向樹的結(jié)構(gòu)。我們可以找出基環(huán)并確定所有外向樹的結(jié)構(gòu)。一條最長路徑有兩種可能：完整地位于某一棵外向樹中；或者位于兩棵外向樹中，其間通過基環(huán)的一段連接。第一種可能可以通過樹形DP解決，問題就在于第二種可能怎樣處理。如果枚舉兩棵外向樹，那就是O(n2),就不可以接受了。我們考慮破環(huán)為鏈，然后將鏈整體左移，制作一個副本。比方說，如果原來的環(huán)是：以1為首破環(huán)，得：以1為首破環(huán)，得：1--2--3--4，然后制作副本，得2--3--4--1--2--3--4，制作副本的主要目的是使得對于每一個點的方程都有統(tǒng)一的形式，使得環(huán)上所有片段都可以對應鏈上的一個片段。這種情況下，用g[x]表示x點上外向樹上的最長下降路的長度，f(x)表示以該點為終點的總最長路徑的長度，則有：f(x)=max{g[i]+g[x]+dis[i,x]}，其中w函數(shù)即w[i,j=di[s丿顯然滿足i=x-n-1Vi<j<kw,i]+w,j= w通過變換之后就可以變成經(jīng)典模型二。這樣，就在總O(n)的時間內(nèi)解決了本題。如果還嫌以上兩個問題不夠典型，下面舉一個典型到所有OIer都耳熟能詳?shù)念}目。例題5：有限背包問題。題目來源：經(jīng)典問題。題目大意：有N件物品，每一件物品的價值為p[k]，重量為w[k]，最多只能選取m[k]次；現(xiàn)在給出背包的最大承重量C,要求在滿足重量要求的條件下使得背包中的物品價值總和最大。分析：如果m[k]=1或者m[k]=+s,就都很好做。但現(xiàn)在m[k]是一個有界值，就比較麻煩了。我們還是按照背包問題的常見思路，一次枚舉每一個物品。設當前枚舉的物品編號為k,用f(x)表示：為了到達價值x,背包的重量至少應該是多少；則我們有：f(x)二min[f(x-i*p[k])+i*w[k]}，這個方程很麻煩，因為某一個狀態(tài)的決策不是連續(xù)i=1的，而是間斷性的。怎樣把決策區(qū)間變成一段連續(xù)區(qū)間呢？很容易想到等價類的思想；如果按照模p[k]對所有的f(x)劃分等價類，那么在同一個等價類中，決策區(qū)間就是連續(xù)的了，我們不妨把新函數(shù)設為h(x)，則方程變?yōu)椋簒-1h(x)=min{h(i)+w[k]*(x-i)}，其中，w函數(shù)即w[i,j]=w'[k]*(-i顯然滿足i=x-m[k]Vi<j<k,w[i,j]+w[j,k]=w[i,k]，(注意w'k]是一個與i和j無關(guān)的常量)經(jīng)過適當?shù)淖兓罂梢赞D(zhuǎn)化為經(jīng)典模型二。于是有限背包問題可以在O(NP)的時間內(nèi)解決，其中P是背包可能取到的最大價值。(其實換成重量也一樣)，這也就是“背包十講”中所說的那個單調(diào)隊列法。我們注意到，如果m[k]=1的話，那么每一個f(x)的決策量都是0(1),這沒什么問題；但如果m[k]=+R,有意味著什么呢？仔細觀察可以發(fā)現(xiàn)，這實際上就拿掉了方程中的循環(huán)變x-1量的下界，對應的是f(x)=min{g(k)}+w[1,x]這樣的一個方程，這顯然是很簡單的，適k=1用單變量打擂臺就可以解決了(盡管我們通常并不這樣做)。所以說，借助經(jīng)典模型二，我們在一個更高的高度上統(tǒng)一了0-1、有限、無限三大背包問題。下面我們再次來看一下例題2《土地購買》中的那個方程：f(n)=mil"(k)+x[n]*y[k+1]},我們來仔細地觀察這個方程：f(k)是變量，y[k+1]是常k=0量，但不論怎么說，這兩個量在以后的計算中都不會變化。而x[n]是一個比例系數(shù)，它與k無關(guān)，只隨著x的變化而變化。如果我們建立平面直角坐標系，以f(k)作為橫軸，y[k+1]作為縱軸，則每一個狀態(tài)f(k)都可以看作是該坐標系中的一個點。在求解狀態(tài)f(n)的過程中，我要求最小化：minP=x+ky，其中x,y是我建立的直角坐標系中某一個點的坐標(表示一個決策)，k就是方程中的x[n]，是只與n有關(guān)，而與決策無關(guān)的一個常量。這個最小化問題是什么呢？其實就是一個平面上的線性規(guī)劃。我們把式子改寫成：1 P 1y=-丁x+，就演變成了這樣的一個問題：在一個直線簇y=-丁x+C中，選取一條直k k k線，使得這條直線過某個給出的數(shù)據(jù)點，同時c要最小。既然問題變成了這么有意思的線性規(guī)劃問題，就有必要進一步的研究，看看是不時有更好的解法，這就導致了我們的另一個經(jīng)典模型：經(jīng)典模型三： f(x)=min{a[x]*f(i)+b[x]*g(i)}oi=1注意：這個模型寫的比較抽象，其實它的涵蓋范圍是很廣的。首先，a[x],b[x]不一定要是常量，只要他們與決策無關(guān)，都可以接受；另外，f(i)和g(i)不管是常量還是變量都沒有關(guān)系，只要他們是一個有最優(yōu)的f(x)決定的二元組就可以了。因此，為了方便描述，我們把這個模型寫成下面這個形式：f(n)=niin{a[n]*x(i)+b[n]*y(i)}i=1 ，其中，x(i)，y(i)都是可以在常數(shù)時間內(nèi)通過f(i)唯一決定的二元組。這個經(jīng)典模型怎樣轉(zhuǎn)化求解呢？前文說過，這樣的模型的求解與平面上的線性規(guī)劃有關(guān)，我們以x(i)為橫軸，y(i)為縱軸建立平面直角坐標系，這樣一個狀態(tài)f(i)所決定的二元組就可以用坐標系中的一個點表示。然后，我們的目標是：aPminP=ax-b，其中a=a[n],b=b[n]，化成：y二一丁x+〒，假設b>0(反之亦bb然)，則我們的任務是使得這條直線的縱截距最小。可以想象有一組斜率相同的直線自負無窮向上平移，所碰到的第一個數(shù)據(jù)點就是最優(yōu)決策。這個時候，有一個重要的性質(zhì)，那就是：所有最優(yōu)決策點都在平面點集的凸包上。基于這個事實，我們可以開發(fā)出很多令人滿意的算法。這時，根據(jù)直線斜率與數(shù)據(jù)點分布的特征，可以劃分為兩種情況：情況一：決策直線的斜率與二元組的橫坐標同時滿足單調(diào)性。(具體的單調(diào)性視最優(yōu)化目標的性質(zhì)而定)這樣的模型是比較好處理的，因為這個時候由于斜率變化是單調(diào)的，所以決策點必然在凸殼上單調(diào)移動。我們只需要維護一個單調(diào)隊列和一個決策指針，每次決策時作這樣幾件事：1、 決策指針(也就是隊首)后移，直至最佳決策點。2、 進行決策。3、 將進行決策之后的新狀態(tài)的二元組加入隊尾，同時作Graham-Scan式的更新操作維護凸殼。(注意此時當前指針所在二元組有可能被拋棄)算法的時間復雜度為O(n)情況二：沒有任何限制。這時問題的解決就比較困難了。顯然，決策點還是應該在凸殼上。我們不妨考慮一個單調(diào)減的凸殼，這個凸殼上點與點之間的連線必然滿足這樣的性質(zhì)：斜率單調(diào)減。通過細致的觀察我們可以發(fā)現(xiàn)，對于一個給定的斜率k來說，對應的直線簇中具有最大縱截距的直線通過的決策點必然滿足這樣的性質(zhì)：該點兩側(cè)的邊的斜率k1,k2滿足k1>k>k2。這樣，我們就可以通過二分查找來確定最佳的決策點。但是，在插入數(shù)據(jù)點的過程中，我們遇到的麻煩可能更大。首先，肯定是二分查找確定橫坐標的插入點，然后對兩側(cè)分別進行Graham維護凸性。但接下來的問題就嚴重了：在維護凸形的過程中我們肯定刪掉了一些點，怎樣重新得到一個完整的凸殼決策表呢？使用move是一個折中的辦法，但是這與理論的時間復雜度分析根本無益。完美的解決方法是應用平衡二叉樹。我們以橫坐標為關(guān)鍵字建立平衡二叉樹，這樣查找和插入的過程都可以在O(logn)時間內(nèi)完成。當我們做Graham維護時，首先將新數(shù)據(jù)點Splay到根節(jié)點，此時剩下的節(jié)點必然分居左子樹和右子樹。然后，我們以左子樹為例，后序遍歷依次查找節(jié)點，直至查找到一個滿足凸形的節(jié)點。將這個節(jié)點Splay到根節(jié)點的左孩子，然后刪掉這個節(jié)點的右孩子。這樣的算法的時間復雜度是O(nlogn)，但是實現(xiàn)起來非常復雜。下面我們來看幾個例題。例題6：《玩具裝箱》的線性算法。例題1中《玩具裝箱》的動態(tài)規(guī)劃方程為：f(x)=miif{i壬X-(-+51ck-L2],下面，我們試圖通過數(shù)學變換將其變成經(jīng)i=l k=i+i典模型三。為了簡化計算，設sum[x]=工c[x]，貝y：i=1f(x)=rniin{f(i)+(x-i-1-L+sum[x]-sum[i])2}i=i=mx1inf{i(+)s(u(mx[+]-xL--1)s(um+i2[]，i))}i=1不妨設a[x]=sum[x]+x-1-1,b[i]=sum[i]+i，顯然這兩個量都是常量，貝y：f(x)=min{f(i)+(a[x]-b[i])2}i=1=mxi1n{f(i)+a2[x]+b2[i]-2a[x]b[i]}i=1 ，=mxi1n{f(i)+b2[i]-2a[x]b[i]}+a2[x]i=1然后問題就明朗了，設平面直角坐標系中x(i)=b[i],y(i)=f(i)+b2[i]，則問題變成:minP=2ax+y，其對應的線性規(guī)劃的目標直線為y=-2ax+P。回顧定義不難看出，a[x]隨著x的增大而增大，x(i)也隨著i的增大而增大。因此，問題中直線斜率單調(diào)減，數(shù)據(jù)點橫坐標單調(diào)增，符合經(jīng)典模型三種的情形1。使用單調(diào)隊列維護凸殼可以在O(n)的時間內(nèi)解決本題。例題七：貨幣兌換。題目來源：NOI2007題目大意：有3種貨幣體系：人民幣，A券，B券，其中A券與B券的價格在每一天都是不同的。在某一天D,你可以做3件事情：1、 如果你的手頭上有A券或B券，你可以將它們都按照當天的價格換成人民幣。2、 如果你的手頭上有人民幣,你可以將它們按照一個特定的比例Rate并以照當天的價格換成A券和B券(就是說你兌換的A券和B券的價值比是Rate)3、什么也不做。一開始你有一些人民幣，請你通過最佳的操作方式在最后一天結(jié)束的時候手頭上握有最多的人民幣。分析：試題中的Hint已經(jīng)告訴我們，如果我們想買進人民幣，就必須全額買進；如果我們想賣出人民幣，就必須全額賣出。由于不管是在哪一天，人民幣總是越多越好；我們用f(n)表示到了第n天最多可能持有的人民幣數(shù)量，用x(i)和y(i)表示在第i天，用最多的錢能夠換成的A券和B券。(注意：由于Rate確定，兌換金額確定，所以A券和B券的數(shù)量是唯一確定的)，我們有：f(n)=nia1x{a[n]*x(i)+b[n]*y(i)}，其中a[n]和b[n]代表A券和B券在第n天的牌價。這個方程式符合經(jīng)典模型三中的情形二。所以，我們應該使用一個平衡樹來維護凸形。時間復雜度是O(nlogn)。由于數(shù)據(jù)弱，所以這道題目用move也是可以搞定的。這篇文章中，我們著重討論了這樣三類經(jīng)典模型的建立與求解過程：經(jīng)典模型一：f(x)二rminff(i)+w[i,x]}，w[i,x]滿足決策單調(diào)性。i=1經(jīng)典模型二：f(x)=mih{g(i)}+w[x]，其中b[x]單調(diào)增。i=b[x]經(jīng)典模型三：f(n)=niin{a[n]*x(i)+b[n]*y(i)}，其中x(i),y(i)可以由f(i)在常數(shù)i=1時間內(nèi)唯一確定。這三類模型都可以在至少O(nlogn)的時間內(nèi)解決，從而起到了對1D/1D的方程的優(yōu)化作用。另外，這三種模型并不是孤立存在的，而是可以互相轉(zhuǎn)化的，文中的很多例題就兼具多種模型的特點。當然，本文只是對1D/1D動態(tài)規(guī)劃優(yōu)化的很初步很淺顯的探討，