動態(tài)規(guī)劃經(jīng)典教程完整版

動態(tài)規(guī)劃經(jīng)典教程引言：本人在做過一些題目后對DP有些感想，于是寫了這個總結(jié)：第一節(jié)動態(tài)規(guī)劃基本概念一，動態(tài)規(guī)劃三要素：階段，狀態(tài)，決策。他們的概念到處都是，我就不多說了，我只說說我對他們的理解：如果把動態(tài)規(guī)劃的求解過程看成一個工廠的生產(chǎn)線，階段就是生產(chǎn)某個商品的不同的環(huán)節(jié)，狀態(tài)就是工件當(dāng)前的形態(tài)，決策就是對工件的操作。顯然不同階段是對產(chǎn)品的一個前面各個狀態(tài)的小結(jié)，有一個個的小結(jié)構(gòu)成了最終的整個生產(chǎn)線。每個狀態(tài)間又有關(guān)聯(lián)（下一個狀態(tài)是由上一個狀態(tài)做了某個決策后產(chǎn)生的）。下面舉一個例子：要生產(chǎn)一批雪糕，在這個過程中要分好多環(huán)節(jié)：購買牛奶，對牛奶提純處理，放入工廠加工，加工后的商品要包裝，包裝后就去銷售……，這樣沒個環(huán)節(jié)就可以看做是一個階段；產(chǎn)品在不同的時候有不同的狀態(tài)，剛開始時只是白白的牛奶，進入生產(chǎn)后做成了各種造型，從冷凍庫拿出來后就變成雪糕（由液態(tài)變成固態(tài)=_=11）。每個形態(tài)就是一個狀態(tài)，那從液態(tài)變成固態(tài)經(jīng)過了冰凍這一操作，這個操作就是一個決策。一個狀態(tài)經(jīng)過一個決策變成了另夕'一個狀態(tài)，這個過程就是狀態(tài)轉(zhuǎn)移，用來描述狀態(tài)轉(zhuǎn)移的方程就是狀態(tài)轉(zhuǎn)移方程。經(jīng)過這個例子相信大家對動態(tài)規(guī)劃有所了解了吧。下面在說說我對動態(tài)規(guī)劃的另外一個理解：用圖論知識理解動態(tài)規(guī)劃：把動態(tài)規(guī)劃中的狀態(tài)抽象成一個點，在有直接關(guān)聯(lián)的狀態(tài)間連一條有向邊，狀態(tài)轉(zhuǎn)移的代價就是邊上的權(quán)。這樣就形成了一個有向無環(huán)圖AOE網(wǎng)（為什么無環(huán)呢？往下看）對這個圖進行拓撲排序，刪除一個邊后同時出現(xiàn)入度為0的狀態(tài)在同一階段。這樣對圖求最優(yōu)路徑就是動態(tài)規(guī)劃問題的求解。二，動態(tài)規(guī)劃的適用范圍動態(tài)規(guī)劃用于解決多階段決策最優(yōu)化問題，但是不是所有的最優(yōu)化問題都可以用動態(tài)規(guī)劃解答呢？一般在題目中出現(xiàn)求最優(yōu)解的問題就要考慮動態(tài)規(guī)劃了，但是否可以用還要滿足兩個條件：最優(yōu)子結(jié)構(gòu)（最優(yōu)化原理）無后效性最優(yōu)化原理在下面的最短路徑問題中有詳細的解答；什么是無后效性呢？就是說在狀態(tài)i求解時用到狀態(tài)j而狀態(tài)j就解有用到狀態(tài)k..?..狀態(tài)N。而求狀態(tài)N時有用到了狀態(tài)i這樣求解狀態(tài)的過程形成了環(huán)就沒法用動態(tài)規(guī)劃解答了，這也是上面用圖論理解動態(tài)規(guī)劃中形成的圖無環(huán)的原因。也就是說當(dāng)前狀態(tài)是前面狀態(tài)的完美總結(jié)，現(xiàn)在與過去無關(guān)。。當(dāng)然，有是換一個劃分狀態(tài)或階段的方法就滿足無后效性了，這樣的問題仍然可以用動態(tài)規(guī)劃解。三，動態(tài)規(guī)劃解決問題的一般思路。拿到多階段決策最優(yōu)化問題后，第一步要判斷這個問題是否可以用動態(tài)規(guī)劃解決，如果不能就要考慮搜索或貪心了。當(dāng)卻定問題可以用動態(tài)規(guī)劃后，就要用下面介紹的方法解決問題了：（1）模型匹配法：最先考慮的就是這個方法了。挖掘問題的本質(zhì)，如果發(fā)現(xiàn)問題是自己熟悉的某個基本的模型，就直接套用，但要小心其中的一些小的變動，現(xiàn)在考題辦都是基本模型的變形套用時要小心條件，三思而后行。這些基本模型在先面的分類中將一一介紹。（2）三要素法仔細分析問題嘗試著確定動態(tài)規(guī)劃的三要素，不同問題的卻定方向不同：先確定階段的問題：數(shù)塔問題，和走路問題（詳見解題報告）先確定狀態(tài)的問題：大多數(shù)都是先確定狀態(tài)的。先確定決策的問題：背包問題。（詳見解題報告）一般都是先從比較明顯的地方入手，至于怎么知道哪個明顯就是經(jīng)驗問題了，多做題就會發(fā)現(xiàn)。（3）尋找規(guī)律法：這個方法很簡單，耐心推幾組數(shù)據(jù)后，看他們的規(guī)律，總結(jié)規(guī)律間的共性，有點貪心的意思。（4）邊界條件法找到問題的邊界條件，然后考慮邊界條件與它的領(lǐng)接狀態(tài)之間的關(guān)系。這個方法也很起效。（5）放寬約束和增加約束這個思想是在陳啟鋒的論文里看到的，具體內(nèi)容就是給問題增加一些條件或刪除一些條件使問題變的清晰。第二節(jié)動態(tài)規(guī)劃分類討論這里用狀態(tài)維數(shù)對動態(tài)規(guī)劃進行了分類:狀態(tài)是一維的1.1下降/非降子序列問題：問題描述：｛挖掘題目的本質(zhì)，一但抽象成這樣的描述就可以用這個方法解｝在一個無序的序列al,a2,a3,a4?.?an里，找至j一個最長的序列滿足：aiv=ajv=ak...v=am，且ivjvk...vm.(最長非降子序列)或ai>aj>ak...>am,且i>j>k...>m.(最長下降子序列)。問題分析：如果前i-1個數(shù)中用到ak(ak>ai或ak<=ai)構(gòu)成了一個的最長的序列加上第I個數(shù)ai就是前i個數(shù)中用到i的最長的序列了。那么求用到ak構(gòu)成的最長的序列有要求前k-1個數(shù)中……從上面的分析可以看出這樣劃分問題滿足最優(yōu)子結(jié)構(gòu)，那滿足無后效性么？顯然對于第i個數(shù)時只考慮前i-1個數(shù)，顯然滿足無后效性，可以用動態(tài)規(guī)劃解。分析到這里動態(tài)規(guī)劃的三要素就不難得出了：如果按照序列編號劃分階段，設(shè)計一個狀態(tài)opt[i]表示前i個數(shù)中用到第i個數(shù)所構(gòu)成的最優(yōu)解。那么決策就是在前i-1個狀態(tài)中找到最大的opt[j]使得aj>ai(或ajv=ai),opt[j]+1就是opt[i]的值；用方程表示為：｛我習(xí)慣了這種寫法，但不是狀態(tài)轉(zhuǎn)移方程的標(biāo)準(zhǔn)寫法｝opt[i]=max(opt[j])+1(0<=j<i且aj<=ai)｛最長非降子序列｝opt[i]=max(opt[j])+1(0<=j<i且aj>ai)｛最長下降子序列｝實現(xiàn)求解的部分代碼：opt[0]:=maxsize；｛maxsize為maxlongint或-maxlongint｝fori:=1tondoforj:=0toi-1doif(a[j]>a[i])and(opt[j]+1>opt[i])thenopt[i]:=opt[j]+1;ans:=-maxlongint;fori:=1tondoifopt[i]>ansthenans:=opt[i];｛ans為最終解｝復(fù)雜度：從上面的實現(xiàn)不難看出時間復(fù)雜度為O(N2),空間復(fù)雜度O(N);例題1攔截導(dǎo)彈I(missile.pas/c/cpp)來源：N0IP1999(提高組)第一題【問題描述】某國為了防御敵國的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達捕捉到敵國的導(dǎo)彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。輸入導(dǎo)彈依次飛來的高度(雷達給出的高度數(shù)據(jù)是不大于30000的正整數(shù))，計算這套系統(tǒng)最多能攔截多少導(dǎo)彈,，如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)?！据斎胛募縨issile.in單獨一行列出導(dǎo)彈依次飛來的高度?！据敵鑫募縨issile.out兩行，分別是最多能攔截的導(dǎo)彈數(shù)，要攔截所有導(dǎo)彈最少要配備的系統(tǒng)數(shù)【輸入樣例】38920715530029917015865【輸出樣例】62【問題分析】有經(jīng)驗的選手不難看出這是一個求最長非升子序列問題，顯然標(biāo)準(zhǔn)算法是動態(tài)規(guī)劃。以導(dǎo)彈依次飛來的順序為階段，設(shè)計狀態(tài)opt[i]表示前i個導(dǎo)彈中攔截了導(dǎo)彈i可以攔截最多能攔截到的導(dǎo)彈的個數(shù)。狀態(tài)轉(zhuǎn)移方程：opt[i]=max(opt[j])+1(h[i]>=h[j],0=vjvi)｛h[i]存，第i個導(dǎo)彈的高度｝最大的opt[i]就是最終的解。這只解決了第一問，對于第二問最直觀的方法就是求完一次opt[i]后把剛才要打的導(dǎo)彈去掉，在求一次opt[i]直到打完所有的導(dǎo)彈，但這樣做就錯了。不難舉出反例：61732錯解：632/1/7正解：61/732其實認真分析一下題就回發(fā)現(xiàn)：每一個導(dǎo)彈最終的結(jié)果都是要被打的，如果它后面有一個比它高的導(dǎo)

彈，那打它的這個裝置無論如何也不能打那個導(dǎo)彈了，經(jīng)過這么一分析，這個問題便抽象成在已知序列里求最長上升序列和上面說的求最長非升序列是一樣的，這里就不多說了。找最長上升序列的問題。復(fù)雜度：

【源代碼】programmissile;constfin='missile.in';fout='missile.out';maxn=10000;vara,opt:array[O..maxn]oflongint;n,anslen,anstime:longint;procedureinit;varx:longint;beginassign(input,fin);reset(input);assign(output,fout);rewrite(output);找最長上升序列的問題。復(fù)雜度：

【源代碼】programmissile;constfin='missile.in';fout='missile.out';maxn=10000;vara,opt:array[O..maxn]oflongint;n,anslen,anstime:longint;procedureinit;varx:longint;beginassign(input,fin);reset(input);assign(output,fout);rewrite(output);n:=0;repeatinc(n);read(a[n]);untilseekeof;end;proceduremain;vari,j:longint;beginfillchar(opt,sizeof(opt),O);a[0]:=maxlongint;fori:=1tondoforj:=i-1downto0doif(a[j]>=a[i])and(opt[j]+1>opt[i])thenopt[i]:=opt[j]+1;anslen:=0;fori:=1tondoifopt[i]>anslenthenanslen:=opt[i];fillchar(opt,sizeof(opt),0);a[O]:=-maxlongint;fori:=1tondoforj:=i-1downto0doif(a[j]<a[i])and(opt[j]+1>opt[i])thenopt[i]:=opt[j]+1;anstime:=0;fori:=1tondoifopt[i]>anstimethenanstime:=opt[i];end;procedureprint;beginwriteln(anslen);writeln(anstime);close(input);close(output);end;begininit;main;print;end.例題二合唱隊形(chorus.pas/c/cpp)來源：NOIP2004(提高組)第一題N位同學(xué)站成一排，音樂老師要請其中的(N-K)位同學(xué)出列，使得剩下的K位同學(xué)排成合唱隊形。合唱隊形是指這樣的一種隊形：設(shè)K位同學(xué)從左到右依次編號為1，2…，K,他們的身高分別為T1，T2,…，TK，則他們的身高滿足T1v...vTi>Ti+1>..?>TK(1v=iv=K)。你的任務(wù)是，已知所有N位同學(xué)的身高，計算最少需要幾位同學(xué)出列，可以使得剩下的同學(xué)排成合唱隊形?！据斎胛募枯斎胛募horus.in的第一行是一個整數(shù)N(2v=Nv=100),表示同學(xué)的總數(shù)。第一行有n個整數(shù)，用空格分隔，第i個整數(shù)Ti(130v=Tiv=230)是第i位同學(xué)的身高(厘米)?！据敵鑫募枯敵鑫募horus.out包括一行，這一行只包含一個整數(shù)，就是最少需要幾位同學(xué)出列?！緲永斎搿?186186150200160130197220【樣例輸出】4【數(shù)據(jù)規(guī)模】對于50%的數(shù)據(jù)，保證有n<=20;對于全部的數(shù)據(jù)，保證有n<=100?！締栴}分析】出列人數(shù)最少，也就是說留的人最多，也就是序列最長。這樣分析就是典型的最長下降子序列問題。只要枚舉每一個人站中間時可以的到的最優(yōu)解。顯然它就等于，包括他在內(nèi)向左求最長上升子序列，向右求最長下降子序列。我們看一下復(fù)雜度：計算最長下降子序列的復(fù)雜度是O(N2),—共求N次，總復(fù)雜度是O(N3)。這樣的復(fù)雜度對于這個題的數(shù)據(jù)范圍來說是可以AC的。但有沒有更好的方法呢？其實最長子序列只要一次就可以了。因為最長下降(上升)子序列不受中間人的影響。只要用OPT1求一次最長上升子序列，OPT2求一次最長下降子序列。這樣答案就是N-max(opt1[i]+opt2[i]-1).復(fù)雜度由O(N3)降到了O(N2)【源代碼】programchorus;constfin='chorus.in';fout='chorus.out';maxn=200;【源代碼】programchorus;constfin='chorus.in';fout='chorus.out';maxn=200;varopt1,opt2,a:array[0..maxn]oflongint;n,ans:longint;beginans:=opt1[i]+opt2[i];procedureinit;a[0]:=-maxlongint;end;varfori:=1tondoprocedureprint;i:longint;forj:=i-1downto0dobeginbeginif(a[j]<a[i])andwriteln(n-ans+1);assign(input,fin);(opt1[j]+1>opt1[i])thenclose(input);reset(input);opt1[i]:=opt1[j]+1;close(output);assign(output,fout);a[n+1]:=-maxlongint;end;rewrite(output);fori:=ndownto1dobeginreadln(n);forj:=i+1ton+1doinit;fori:=1tondoif(a[j]<a[i])andmain;read(a[i]);(opt2[j]+1>opt2[i])thenprint;end;opt2[i]:=opt2[j]+1;ceduremain;ans:=0;varfori:=1tondoi,j:longint;ifopt1[i]+opt2[i]>ansthen例題3BuyLowBuyLowe*(buylow.pas/c/cpp)來源：USACO4-3-1【問題描述】“逢低吸納”是炒股的一條成功秘訣。如果你想成為一個成功的投資者，就要遵守這條秘訣"逢低吸納，越低越買"這句話的意思是：每次你購買股票時的股價一定要比你上次購買時的股價低.按照這個規(guī)則購買股票的次數(shù)越多越好，看看你最多能按這個規(guī)則買幾次。給定連續(xù)的N天中每天的股價。你可以在任何一天購買一次股票，但是購買時的股價一定要比你上次購買時的股價低。寫一個程序，求出最多能買幾次股票。以下面這個表為例，某幾天的股價是：天數(shù)123456789101112股價686954646864706778629887這個例子中，聰明的投資者(按上面的定義)，如果每次買股票時的股價都比上一次買時低，那么他最多能買4次股票。一種買法如下(可能有其他的買法)：天數(shù)25610股價69686462【輸入文件】buylow.in第1行:N(1<=N<=5000),表示能買股票的天數(shù)。第2行以下：N個正整數(shù)(可能分多行)，第i個正整數(shù)表示第i天的股價.這些正整數(shù)大小不會超過longint(pascal)/long(c++).【輸出文件】buylow.out只有一行，輸出兩個整數(shù)：能夠買進股票的天數(shù)長度達到這個值的股票購買方案數(shù)量在計算解的數(shù)量的時候，如果兩個解所組成的字符串相同，那么這樣的兩個解被認為是相同的(只能算做一個解)。因此，兩個不同的購買方案可能產(chǎn)生同一個字符串，這樣只能計算一次?！据斎霕永?2686954646864706778629887【輸出樣例】2【問題分析】從題目描述就可以看出這是最長下降子序列問題，于是求解第一問不是難事，以天數(shù)為階段，設(shè)計狀態(tài)opt[i]表示前i天中要買第i天的股票所能得到的最大購買次數(shù)。狀態(tài)轉(zhuǎn)移方程：opt[i]=max(opt[j])+1(a[i]>=a[j],0=<j<i){a[i]存第i天股價}最大的opt[i]就是最終的解。第二問呢，稍麻煩一點。從問題的邊界出發(fā)考慮問題，當(dāng)?shù)谝粏柷蟮靡粋€最優(yōu)解opt[i]=X時，在1到N中如果還有另外一個opt[j]=x那么選取J的這個方案肯定是成立的。是不是統(tǒng)計所有的opt[j]=x的個數(shù)就是解了呢？顯然沒那么簡單，因為選取J這天的股票構(gòu)成的方案不見得=1,看下面一個例子：64312方案一：5431

方案二：5432方案三：6431方案四：6432x=4也就是所雖然opt⑸=X和opt[6]=X但個數(shù)只有兩個，而實際上應(yīng)該有四個方案，但在仔細觀察發(fā)現(xiàn),構(gòu)成opt[5]=x的這個方案中opt[j]=x-1的方案數(shù)有兩個,opt[j]=x-2的有一個，opt[j]=x-3的有一個顯然這是滿足低歸定義的設(shè)計函數(shù)F(i)表示前I張中用到第i張股票的方案數(shù)。遞推式：(i=0)F(i)=Sum(F(j))(0<=j<=n,a[j]>a[i],opt[j]=opt[i]-1){sum代表求和}答案=sum(F(j)){0<j<=n,opt[j]=x}復(fù)雜度：求解第一問時間復(fù)雜度是O(N2),求解第二問如果用遞推或遞歸+記憶化時間復(fù)雜度仍為O(N2)但要是用赤裸裸的遞歸那就復(fù)雜多了……，因為那樣造成了好多不必要的計算。你認為這樣做就解決了這道題目了么？還沒有，還要注意一些東西：如果有兩個方案中出現(xiàn)序列一樣，視為一個方案，要需要加一個數(shù)組next用next[i]記錄和第i個數(shù)情況一樣(即：opt[i]=opt[j]且a[i]=a[j])可看做一個方案的最近的位置。遞推時j只要走到next[i]即可。為了方便操作可以將a[n+1]賦值為-maxlongint這樣可以認為第n+1個一定可以買，答案就是sum(F(n+l))。(sum(F(n+l))。(3)看數(shù)據(jù)規(guī)模顯然要用高精注：USACO上最后一個點錯了【源代碼】programbuylow;constfin='buylow.in';fout='buylow.out';maxn=5010;maxsize=10;jz=1OOOOOOOO;typearrtype=array[0..maxsize]oflongint;vara,opt,next:array[0..maxn]oflongint;F:array[0..maxn]ofarrtype;n:longint;procedureinit;vari:longint;beginassign(input,fin);reset(input);assign(output,fout);rewrite(output);readln(n);ifn=5then{最后一個點錯了，我只好這么寫了}beginwriteln('25');close(input);close(output);halt;end;fori:=1tondoread(a[i]);。我在程序中做了處理。end;procedureHinc(varx:arrtype;y:arrtype);vari,z:longint;beginz:=0;fori:=1tomaxsizedobeginz:=zdivjz+x[i]+y[i];x[i]:=zmodjz;end;end;proceduremain;vari,j:longint;begina[0]:=maxlongint;a[n+1]:=-maxlongint;fori:=1ton+1doforj:=0toi-1doif(a[j]>a[i])and(opt[j]+1>opt[i])thenopt[i]:=opt[j]+1;fori:=1tondobeginj:=i-1;while(j>0)and((opt[i]<>opt[j])or(a[i]<>a[j]))dodec(j);next[i]:=j;end;F[0,1]:=1;fori:=1ton+1doforj:=i-1downtonext[i]doif(opt[j]=opt[i]-1)and(a[j]>a[i])thenHinc(F[i],F[j]);end;procedureprint;vari,top,m:longint;beginwrite(opt[n+1]-1,'');top:=maxsize;while(top>1)and(F[n+1][top]=0)dodec(top);write(F[n+1,top]);fori:=top-1downto1dobeginm:=F[n+1,i];whilem<maxsizediv10dobeginwrite('O');m:=m*10;end;write(F[n+1,i]);end;writeln;close(input);close(output);end;begininit;main;print;end.例題4船(ships.pas/c/cpp)例題4船【問題描述】PALMIA國家被一條河流分成南北兩岸，南北兩岸上各有N個村莊。北岸的每一個村莊有一個唯一的朋友在南岸，且他們的朋友村莊彼此不同。每一對朋友村莊想要一條船來連接他們，他們向政府提出申請以獲得批準(zhǔn)。由于河面上常常有霧，政府決定禁止船只航線相交（如果相交，則很可能導(dǎo)致碰船）。你的任務(wù)是編寫一個程序，幫助政府官員決定批準(zhǔn)哪些船只航線，使得不相交的航線數(shù)目最大?！据斎胛募縮hips.in輸入文件由幾組數(shù)據(jù)組成。每組數(shù)據(jù)的第一行有2個整數(shù)X，Y，中間有一個空格隔開,X代表PALMIA河的長度（10v=Xv=6000）,Y代表河的寬度（10v=Yv=100）。第二行包含整數(shù)N,表示分別坐落在南北兩岸上的村莊的數(shù)目（1v=Nv=5000）。在接下來的N行中，每一行有兩個非負整數(shù)C，D,由一個空格隔開，分別表示這一對朋友村莊沿河岸與PALMIA河最西邊界的距離（C代表北岸的村莊，D代表南岸的村莊），不存在同岸又同位置的村莊。最后一組數(shù)據(jù)的下面僅有一行，是兩個0，也被一空格隔開?！据敵鑫募縮hips.out對輸入文件的每一組數(shù)據(jù)，輸出文件應(yīng)在連續(xù)的行中表示出最大可能滿足上述條件的航線的數(shù)目。【輸入樣例】3047224610315129817174200【輸出樣例】4【問題分析】這道題目相對來說思考難度較高，從字面意義上看不出問題的本質(zhì)來，有點無法下手的感覺。這里我給大家推薦兩種思考這類問題的方法。法一：尋找規(guī)律法（我前面總結(jié)提到的第3個方法）仔細觀察上圖：紅色航線是合法的，那么他們滿足什么規(guī)律呢？C1C2C3C4北岸紅線的端點：491517南岸紅線的端點：281217D1D2D3D4不難看出無論線的斜率如何，都有這樣的規(guī)律：C1<C2<C3<C4且D1<D2<D3<D4如果我們把輸入數(shù)據(jù)排升序，問題變抽象為：在一個序列（D）里找到最長的序列滿足DIvDJvDk……且ivjvk這樣的話便是典型的最長非降子序列問題了。?！ǘ哼吔鐥l件法（我前面總結(jié)提到的第4個方法）邊界法其實就是把數(shù)據(jù)往小了縮，顯然N=1是答案是1。N=2時呢?考慮這樣一組數(shù)據(jù)：N=2C1D1C2D2當(dāng)C1<C2時，如果D1>D2那么一定會相交，反之則不會相交。當(dāng)C1>C2時，如果D1<D2那么一定會相交，反之則不會相交。N=3C1D1C2D2C3D3

其實不用在推導(dǎo)N=3了，有興趣的可以推導(dǎo)去?？碞=2時就能得出：對于任意兩條航線如果滿足CivCj且DivDj則兩條航線不相交。這樣的話要想在一個序列里讓所有的航線都不相交那比然滿足，ClvC2vC3…Cans且DlvD2vD3…vDans，也就是將C排序后求出最長的滿足這個條件的序列的長度就是解。這樣分析后顯然是一個最長非降子序列問題。復(fù)雜度：排序可以用O(nlogn)的算法，求最長非降子序列時間復(fù)雜度是O(n2).總復(fù)雜度為O(n2).【源代碼】i:=L;forj:=0toi-1doprogramships;j:=r;if(a[j].d<a[i].d)andconstx:=a[(i+j)div2].c;(opt[j]+1>opt[i])thenfin='ships.in';repeatopt[i]:=opt[j]+1;fout='ships.out';whilea[i].c<xdoans:=-maxlongint;maxn=5010;inc(i);fori:=1tondotypewhilea[j].c>xdoifans<opt[i]thenretype=recorddec(j);ans:=opt[i];C,D:longint;ifi<=jthenwriteln(ans);end;beginend;vary:=a[i];beginx,y,n,ans:longint;a[i]:=a[j];assign(input,fin);a:array[O..maxn]ofretype;a[j]:=y;reset(input);opt:array[0..maxn]oflongint;inc(i);assign(output,fout);procedureinit;dec(j);rewrite(output);varend;read(x,y);i:longint;untili>j;while(x+y<>0)dobeginifj>Lthenquick(L,j);beginreadln(n);ifi<rthenquick(i,r);init;fori:=1tondoend;main;read(a[i].c,a[i].d);proceduremain;read(x,y);end;varend;procedurequick(L,r:longint);i,j:longint;close(input);varbeginclose(output);i,j,x:longint;fillchar(opt,sizeof(opt),0);end.y:retype;quick(1,n);beginfori:=1tondo1.2背包問題首先說說背包問題的基本模型:現(xiàn)有N個物品，每個物品的價值為V,重量為W。求用一個載重量為S的背包裝這寫物品，使得所裝物品的總價值最高。背包問題用貪心和搜索解，當(dāng)然效果不佳，不過在我的貪心和搜索總結(jié)中會說到。顯然標(biāo)準(zhǔn)的解法是動態(tài)規(guī)化，我在解決這個問題時習(xí)慣設(shè)計一維狀態(tài)，還可以設(shè)計二維的，二維狀態(tài)在下面會講，現(xiàn)在只討論用一維狀態(tài)實現(xiàn)背包問題。背包問題的分類：小數(shù)背包:物品的重量是實數(shù)，如油，水等可以取1.67升……整數(shù)背包：<1>0/1背包：每個物品只能選一次，或不選。不能只選一部分<2>部分背包：所選物品可以是一部分。多重背包：背包不只一個。小數(shù)背包：在貪心總結(jié)中會細講。整數(shù)背包：部分背包：同小數(shù)背包。0/1背包：這個問題是最經(jīng)常出現(xiàn)的問題，應(yīng)該熟練掌握。我們先看一下0/1背包的簡化版：現(xiàn)有N個物品，每個物品重量為W,這些物品能否使在載重量為S的背包裝滿(即重量和正好為S)？如過不能那能使物品重量和最重達到多少針對這一問題我們以物品的個數(shù)分階段，設(shè)計一個狀態(tài)opt[i]表示載重量為i的背包可否裝滿，顯然opt[i]的基類型是boolean。決策是什么呢？當(dāng)要裝第i個物品時，如果前i-1個物品可以使載重為k的背包裝滿，那么載重為k+w[i]的背包就可以裝滿。于是對于一個opt[j]來說，只要opt[j-w[i]]是true（表示可裝滿）那opt[j]就可以裝滿，但要注意：針對每一個物品枚舉背包的載重量時如果這樣正向的推導(dǎo)會使同一個物品用好幾次，因為k+w[i]可裝滿那k+w[i]+w[i]就可裝滿，但實際上是裝不滿的因為物品只有一個。解決這個問題很簡單，只要逆向推導(dǎo)就OK了。這樣劃分階段，設(shè)計狀態(tài)，滿足無后效性和么？顯然對與一個每一個階段都是獨立的，物品的順序并不影響求解，因為裝物品的次序不限。而對于opt[j]只考慮opt[j-w[i]]而不考慮后面的，所以滿足無后效性。有了上面的分析不難寫出狀態(tài)轉(zhuǎn)移方程：opt[j]:=opt[j-w[l]]{opt[j-w[i]]=true}時間復(fù)雜度：階段數(shù)O（S）*狀態(tài)數(shù)（O（N））*轉(zhuǎn)移代價（O⑴）=O（SN）下面看幾個例題：例題5裝箱問題|（pack.pas/c/cpp）來源：N0IP2001（普及組）第四題【問題描述】有一個箱子容量為V（正整數(shù)，0<=V<=20000）,同時有n個物品（0<n<=30=，每個物品有一個體積（正整數(shù)）。要求n個物品中，任取若干個裝入箱內(nèi)，使箱子的剩余空間為最小?！据斎胛募康谝恍幸粋€正整數(shù)V表示箱子的容量，第二行一個正整數(shù)N表示物品個數(shù)，接下來N行列出這N個物品各自的體積?！据敵鑫募繂为氁恍校硎鞠渥幼钚〉氖Ｓ嗫臻g。【輸入樣例】2468312797【輸出樣例】0【問題分析】本題是經(jīng)典的0/1背包問題，并且是0/1背包的簡化版，把箱子看做背包，容量看做載重量，體積看做重量，剩余空間最小也就是盡量裝滿背包。于是這個問題便成了：有一個栽重量為V的背包，有N個物品，盡量多裝物品，使背包盡量的重。設(shè)計一個狀態(tài)opt[i]表示重量i可否構(gòu)成。狀態(tài)轉(zhuǎn)移方程：opt[j]:=opt[j-w[1]]{opt[j-w[i]]=true}最終的解就是V-X(x<=n且opt[x]=true且opt[x+1..n]=false)?！驹创a1】reset(input);opt[j]:=true;programpack;assign(output,fout);x:=v;constrewrite(output);whilenotopt[x]dodec(x);fin='pack.in';read(v);end;fout='pack.out';read(n);procedureprint;maxv=20010;fori:=1tondobeginmaxn=100;read(w[i]);writeln(v-x);varend;close(input);opt:array[0..maxv]ofproceduremain;close(output);boolean;varend;w:array[O..maxn]oflongint;i,j:longint;beginv,n,x:longint;begininit;procedureinit;fillchar(opt,sizeof(opt),false);main;varopt[0]:=true;print;i:longint;fori:=1tondoend.beginforj:=vdowntow[i]doassign(input,fin);ifopt[j-w[i]]then3333例題6祛碼稱重來源：N0IP1996（提高組）第四題【問題描述】設(shè)有l(wèi)g、2g、3g、5g、10g、20g的砝碼各若干枚（其總重<=1000）,用他們能稱出的重量的種類數(shù)?！据斎胛募縜la2a3a4a5a6（表示lg砝碼有al個，2g砝碼有a2個，…，20g砝碼有a6個，中間有空格）?！据敵鑫募縏otal=N（N表示用這些砝碼能稱出的不同重量的個數(shù)，但不包括一個砝碼也不用的情況）?！据斎霕永?10000【輸出樣例】TOTAL=3【問題分析】把問題稍做一個改動，已知a1+a2+a3+a4+a5+a6個砝碼的重量w[i],w[i]E{1,2,3,5,10,20}其中砝碼重量可以相等，求用這些砝碼可稱出的不同重量的個數(shù)。這樣一改就是經(jīng)典的0/1背包問題的簡化版了，求解方法完全和上面說的一樣，這里就不多說了，只是要注意這個題目不是求最大載重量，是統(tǒng)計所有的可稱出的重量的個數(shù)?！驹创a1】【源代碼1】programP4;constmaxn=1010;w:array[1..6]oflongint=(1,2,3,5,10,20);varopt:array[0..maxn]ofboolean;a:array[1..6]oflongint;procedureinit;vari:longint;beginfori:=1to6doread(a[i]);end;proceduremain;vari,j,k:longint;beginfillchar(opt,sizeof(opt),false);opt[0]:=true;fori:=1to6doforj:=1toa[i]dofork:=maxndowntow[i]doifopt[k-w[i]]thenopt[k]:=true;end;procedureprint;varans,i:longint;beginans:=0;fori:=1tomaxndoifopt[i]theninc(ans);writeln(ans);end;begininit;main;print;end.例題7積木城堡|來源：vijosP1059【問題描述】XC的兒子小XC最喜歡玩的游戲用積木壘漂亮的城堡。城堡是用一些立方體的積木壘成的，城堡的每一層是一塊積木。小XC是一個比他爸爸XC還聰明的孩子，他發(fā)現(xiàn)壘城堡的時候，如果下面的積木比上面的積木大，那么城堡便不容易倒。所以他在壘城堡的時候總是遵循這樣的規(guī)則。小XC想把自己壘的城堡送給幼兒園里漂亮的女孩子們，這樣可以增加他的好感度。為了公平起見，他決定把送給每個女孩子一樣高的城堡，這樣可以避免女孩子們?yōu)榱双@得更漂亮的城堡而引起爭執(zhí)?？墒撬l(fā)現(xiàn)自己在壘城堡的時候并沒有預(yù)先考慮到這一點。所以他現(xiàn)在要改造城堡。由于他沒有多余的積木了，他靈機一動，想出了一個巧妙的改造方案。他決定從每一個城堡中挪去一些積木，使得最終每座城堡都一樣高。為了使他的城堡更雄偉，他覺得應(yīng)該使最后的城堡都盡可能的高。任務(wù)：請你幫助小XC編一個程序，根據(jù)他壘的所有城堡的信息，決定應(yīng)該移去哪些積木才能獲得最佳的效果?！据斎胛募康谝恍惺且粋€整數(shù)N（N<=100）,表示一共有幾座城堡。以下N行每行是一系列非負整數(shù)，用一個空格分隔，按從下往上的順序依次給出一座城堡中所有積木的棱長。用-1結(jié)束。一座城堡中的積木不超過100塊，每塊積木的棱長不超過100?！据敵鑫募恳粋€整數(shù)，表示最后城堡的最大可能的高度。如果找不到合適的方案，則輸出0。【輸入樣例】221-121-1【輸出樣例】read(m);end;read(m);end;fori:=1totopdoforj:=tothigdownto1doif(j-a[i]>=0)and(opt[ii,j-a[i]])thenopt[ii,j]:=true;end;ans:=maxhig;whilenotopt[1,ans]dodec(ans);whilenotcan(ans)dodec(ans);writeln(ans);end;begininit;main;end.i:longint;begincan:=true;fori:=1tondoifnotopt[i,m]thenexit(false);end;proceduremain;varii,m,tothig,i,j,ans:longint;beginforii:=1tondobegintop:=0;read(m);tothig:=0;whilem>0dobegininc(top);a[top]:=m;inc(tothig,m);【提交鏈接】/【問題分析】首先要說明一點，可以挪走任意一個積木，不見得是最上面的。初看題目有點茫然，但抽象一下就。。。。。。。。。。其實塔好積木在拿走就相當(dāng)于當(dāng)初搭的時候沒選拿走的積木。這樣一轉(zhuǎn)化思維問題就清楚了。把積木可搭建的最大高度看做背包的載重，每塊積木的高度就是物品的重量。也就是用給定的物品裝指定的包，使每個包裝的物品一樣多，且在符合條件的前提下盡量多。這樣就變成經(jīng)典的背包問題了。對于每一個城堡求一次，最終找到每一個城堡都可達到的最大高度即可?！驹创a1】constmaxhig=7000;maxn=100;varn,top:longint;opt:array[0..maxn,0..maxhig]ofboolean;a:array[O..maxn]oflongint;procedureinit;vari:longint;beginreadln(n);fillchar(opt,sizeof(opt),false);fori:=1tondoopt[i,0]:=true;end;functioncan(m:longint):boolean;var回顧上面的內(nèi)容充分說明動態(tài)規(guī)劃的本質(zhì)就是遞推。其實按照我的理解（動規(guī)涉及最優(yōu)決策，遞推是單純的總結(jié)）背包問題的簡化版更準(zhǔn)確點算是遞推而非動態(tài)規(guī)劃，至于動歸和遞推之間的界線本來就很模糊（至少我這么認為）把它看做什么都可以，沒必要咬文嚼字。回到0/1背包的原問題上（如果你忘了就去上面看看）。如果在不知道這個模型的情況下我們怎么做這個題呢？這就要用到第一節(jié)提到的方法二：三要素法。題目中明確說明對于一個物品要不就拿走要不就放下，其實題目赤裸裸的告訴我們決策就是不拿（用0表示）或拿（用1表示）。這樣想都不用想就知道了決策，這也是本題的突破口。知道了決策寫個搜索的程序應(yīng)該是很輕松的了。那么階段是什么呢？顯然，給你一堆東西讓你往包里塞，你當(dāng)然是一個一個的那來，塞進去。那么階段很明顯就是物品的個數(shù)。狀態(tài)又是什么呢？有的人在裝東西是有個習(xí)慣（比如說我）就是先把東西分類，然后把同類的東西打個小包，最后在把小包放進去，我們可以按這個思想給物品打一些小包，也就是按照單位為1的遞增的順序準(zhǔn)備好多小包，比如載重是6的包，可以為它準(zhǔn)備載重是1，2，3，4，5的小包。這樣狀態(tài)就可以想出來了:設(shè)計狀態(tài)opt[i，j]表示裝第i個物品時載重為j的包可以裝到的最大價值。opt[i-1,j]（j-w[i]<0，i>0）狀態(tài)轉(zhuǎn)移方程：opt[i,j]=max{opt[i-1,j],opt[i-1,j-w[i]]+v[i]}（j-w[i]>=0,i>0）（w[i]:第i個物品的重量，v[i]第i個物品的價值）解釋：要載重為j的背包空出w[i]（j-w[i]）的空間且裝上第i個物品，比不裝獲得的價值大就裝上它。邊界條件：opt[0,i]=0;（iE{1..S}）注：這種二維的狀態(tài)表示應(yīng)該在下節(jié)講，但是為了方便理解先在這里說了。上面的方法動態(tài)規(guī)劃三要素都很明顯，實現(xiàn)也很簡單。但是在我初學(xué)背包時卻用另外一種一維的狀態(tài)表示法。用第一節(jié)說的思考方法五（放寬約束和增加約束）在重新思考一下這個問題：怎么放寬約束呢？把題目中的價值去掉，不考慮價值即最優(yōu)就變成背包問題的簡化版了。那簡化版的求解對我們有何啟示呢？再一次增加約束：背包只能裝滿。顯然對于N個裝滿背包的方案中只要找到一個價值最大的就是問題的解。那么裝不滿怎么辦呢？其實裝不滿背包，它總要達到一定的重量(X)。我們可以把這種情況看作是裝滿一個載重為X的小包?？偨Y(jié)一下上面的思維過程：放寬約束讓我們找到問題的突破口一一和背包問題簡化版一樣，我們可以卻定載重為S的背包是否可以裝滿。增加約束讓我們找到問題的求解方法一一在裝滿背包的方案中選擇最優(yōu)的一個方案。這樣問題就解決了。設(shè)計一個狀態(tài)opt[j]表示裝滿載重為j的背包可獲得的最大價值。對于第i個物品，只要opt[j-w[i]]可以裝滿且opt[j-w[i]]+v[i]比opt[j]大就裝上這個物品(更新opt[j])。怎么使opt[j]既有是否構(gòu)成又有最優(yōu)的概念呢？opt[j]只表示最優(yōu)，只不過使初始條件+1,判斷opt[j]是否為0,如果opt[j]=0說明j裝不滿。邊界條件：opt[0]=1;狀態(tài)轉(zhuǎn)移方程：opt[j]=max{opt[j-w[i]]}(0vivn,w[i]v=jv=S)問題解：ans=max{opt[i]}-1(0viv=s)時間復(fù)雜度：階段數(shù)O(S)*狀態(tài)數(shù)(O(N))*轉(zhuǎn)移代價(O(1))=O(SN)下面看幾個例題：例題8釆藥|(medic.pas/c/cpp)來源：N0IP2005(普及組)第三題【問題描述】辰辰是個天資聰穎的孩子，他的夢想是成為世界上最偉大的醫(yī)師。為此，他想拜附近最有威望的醫(yī)師為師。醫(yī)師為了判斷他的資質(zhì)，給他出了一個難題。醫(yī)師把他帶到一個到處都是草藥的山洞里對他說：“孩子，這個山洞里有一些不同的草藥，采每一株都需要一些時間，每一株也有它自身的價值。我會給你一段時間，在這段時間里，你可以采到一些草藥。如果你是一個聰明的孩子，你應(yīng)該可以讓采到的草藥的總價值最大?！比绻闶浅匠?，你能完成這個任務(wù)嗎？【輸入文件】輸入文件medic.in的第一行有兩個整數(shù)T(1<=T<=1000)和M(1<=M<=100)，用一個空格隔開，T代表總共能夠用來采藥的時間，M代表山洞里的草藥的數(shù)目。接下來的M行每行包括兩個在1到100之間(包括1和100)的整數(shù)，分別表示采摘某株草藥的時間和這株草藥的價值?！据敵鑫募枯敵鑫募edic.out包括一行，這一行只包含一個整數(shù)，表示在規(guī)定的時間內(nèi)，可以采到的草藥的最大總價值。【輸入樣例】310069112【輸出樣例】3【數(shù)據(jù)規(guī)?！繉τ?0%的數(shù)據(jù)，M<=10;對于全部的數(shù)據(jù)，M<=100。【問題分析】這是一道典型的0/1背包問題，把時間看做標(biāo)準(zhǔn)模型中的重量，把規(guī)定的時間看做載重為T的背包這樣問題和基本模型就一樣了，具體實現(xiàn)這里不多說了?！驹创a1】{二維狀態(tài)}t,n:longint;close(input);programmedic;procedureinit;end;constvarfunctionfin='medic.in';i:longint;max(x,y:longint):longint;fout='medic.out';beginbeginmaxt=1010;assign(input,fin);ifx>ythenmax:=xmaxn=110;reset(input);elsemax:=y;varassign(output,fout);end;opt:array[0..maxn,0..maxt]ofrewrite(output);proceduremain;longint;read(t,n);varw,v:array[0..maxn]offori:=1tondoi,j:longint;longint;read(w[i],v[i]);begin

fillchar(opt,sizeof(opt),0);fori:=1tondoforj:=ltotdoifj_w[i]vOthenopt[i,j]:=opt[i-1,j]elseopt[i,j]:=max(opt[i_1,j],opt[i_1,j_w[i]]+v[i])fillchar(opt,sizeof(opt),0);fori:=1tondoforj:=ltotdoifj_w[i]vOthenopt[i,j]:=opt[i-1,j]elseopt[i,j]:=max(opt[i_1,j],opt[i_1,j_w[i]]+v[i])；end;procedureprint;beginwriteln(opt[n,t]);close(output);end;begininit;main;print;end.【源代碼2】｛一維狀態(tài)｝programmedic;constfin='medic.in';fout='medic.out';maxt=1010;maxn=110;varopt:array[O..maxt]oflongint;w,v:array[O..maxn]oflongint;ans,t,n:longint;procedureinit;vari:longint;beginassign(input,fin);reset(input);assign(output,fout);rewrite(output);readln(t,n);fori:=1tondoread(w[i],v[i]);close(input);end;proceduremain;vari,j:longint;beginfillchar(opt,sizeof(opt),0);opt[0]:=1;fori:=1tondoforj:=tdowntow[i]doif(opt[j-w[i]]>0)and(opt[j-w[i]]+v[i]>opt[j])thenopt[j]:=opt[j-w[i]]+v[i];ans:=-maxlongint;fori:=1totdoifopt[i]>ansthenans:=opt[i];end;procedureprint;beginwriteln(ans-1);close(output);end;begininit;main;print;end.例題9開心的金明來源：N0IP2006（普及組）第二題【問題描述】金明今天很開心，家里購置的新房就要領(lǐng)鑰匙了，新房里有一間他自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說：“你的房間需要購買哪些物品，怎么布置，你說了算，只要不超過N元錢就行”。今天一早金明就開始做預(yù)算，但是他想買的東西太多了，肯定會超過媽媽限定的N元。于是，他把每件物品規(guī)定了一個重要度，分為5等：用整數(shù)1~5表示，第5等最重要。他還從因特網(wǎng)上查到了每件物品的價格（都是整數(shù)元）。他希望在不超過N元（可以等于N元）的前提下，使每件物品的價格與重要度的乘積的總和最大。設(shè)第j件物品的價格為v[j]，重要度為w[j]，共選中了k件物品，編號依次為j1...jk,則所求的總和為：v[j1]*w[j1]+..+v[jk]*w[jk]請你幫助金明設(shè)計一個滿足要求的購物單.【輸入文件】輸入的第1行，為兩個正整數(shù)，用一個空格隔開：Nm（其中N（<30000）表示總錢數(shù)，m（v25）為希望購買物品的個數(shù)。）從第2行到第m+1行，第j行給出了編號為j-1的物品的基本數(shù)據(jù)，每行有2個非負整數(shù)vp（其中v表示該物品的價格（v<10000），p表示該物品的重要度（1?5））【輸出文件】輸出只有一個正整數(shù)，為不超過總錢數(shù)的物品的價格與重要度乘積的總和的最大值（<100000000）【輸入樣例】1000580024005300540032002【輸出樣例】3900【問題分析】這仍然是一到典型的0/1背包，只不過注意這個問題中的價值對應(yīng)背包模型中的重量，這個問題中的價值和重要度的成績是背包模型中的價值。（很饒口?。?。具體實現(xiàn)同背包模型一樣，這里不多說了?！驹创a】programp2;constmaxn=30010;maxm=30;varopt:array[0..maxn]oflongint;【源代碼】programp2;constmaxn=30010;maxm=30;varopt:array[0..maxn]oflongint;v,p:array[0..maxm]longint;n,m:longint;procedureinit;vari:longint;beginofreadln(n,m);fori:=1tomdoreadln(v[i],p[i]);end;proceduremain;vari,j:longint;beginfillchar(opt,sizeof(opt),0);opt[0]:=l;fori:=1tomdobeginforj:=ndownto1dobeginbeginfillchar(opt,sizeof(opt),0);opt[0]:=l;fori:=1tomdobeginforj:=ndownto1dobeginif(j-v[i]>=0)and(opt[j-v[i]]>0)and(opt[j-v[i]]+v[i]*p[i]>opt[j])thenopt[j]:=opt[j-v[i]]+v[i]*p[i];end;end;end;procedureprint;vari,ans:longint;beginans:=0;fori:=1tondoifopt[i]>ansthenans:=opt[i];writeln(ans-1);end;begininit;main;print;end.例題10金明的預(yù)算方案|（budget.pas/c/cpp）來源：N0IP2006第二題【問題描述】金明今天很開心，家里購置的新房就要領(lǐng)鑰匙了，新房里有一間金明自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說：“你的房間需要購買哪些物品，怎么布置，你說了算，只要不超過N元錢就行”。今天一早，金明就開始做預(yù)算了，他把想買的物品分為兩類：主件與附件，附件是從屬于某個主件的，下表就是一些主件與附件的例子：主件附件電腦打印機，掃描儀書柜圖書書桌臺燈，文具工作椅無如果要買歸類為附件的物品，必須先買該附件所屬的主件。每個主件可以有0個、1個或2個附件。附件不再有從屬于自己的附件。金明想買的東西很多，肯定會超過媽媽限定的N元。于是，他把每件物品規(guī)定了一個重要度，分為5等：用整數(shù)1?5表示，第5等最重要。他還從因特網(wǎng)上查到了每件物品的價格（都是10元的整數(shù)倍）。他希望在不超過N元（可以等于N元）的前提下，使每件物品的價格與重要度的乘積的總和最大。設(shè)第j件物品的價格為v[j]，重要度為w[j]，共選中了k件物品，編號依次為j1，j2,……，jk，則所求的總和為：v[j1]*w[j1]+v[j2]*w[j2]+???+v[jk]*w[jk]。（其中*為乘號）請你幫助金明設(shè)計一個滿足要求的購物單?！据斎胛募枯斎胛募udget.in的第1行，為兩個正整數(shù)，用一個空格隔開：Nm（其中N（<32000）表示總錢數(shù)，m（<60）為希望購買物品的個數(shù)。）從第2行到第m+1行，第j行給出了編號為j-1的物品的基本數(shù)據(jù)，每行有3個非負整數(shù)：vpq（其中v表示該物品的價格（v<10000）,p表示該物品的重要度（1?5）,q表示該物品是主件還是附件。如果q=0，表示該物品為主件，如果q>0，表示該物品為附件，q是所屬主件的編號【輸出文件】輸出文件budget.out只有一個正整數(shù)，為不超過總錢數(shù)的物品的價格與重要度乘積的總和的最大值（<200000）。【輸入樣例】100058002040051300514003050020【輸出樣例】2200【問題分析】這道題是一道典型的背包問題，比較麻煩的就是它還存在附件和主件之分。但這并不影響解題，由于附件最多兩個，那么我們做一個對主，附件做個捆綁就行了。（1）標(biāo)準(zhǔn)算法因為這道題是典型的背包問題，顯然標(biāo)準(zhǔn)算法就是動態(tài)規(guī)劃。由于我們要對主，附件做捆綁。由于題目沒有直接給出每個主件對應(yīng)的附件，所以還需要做一個預(yù)處理：另開兩個數(shù)組q1，q2來分別記錄對應(yīng)的第i個主件的附件。那么對與附件不需要處理。而主件的花費就有4種情況了。（下面用W表示花費）W1=v[i]（只買主件W2=v[i]+v[q1[i]]（買主件和第一個附件）W3=v[i]+v[q2[i]]（買主件和第二個附件）

W4=v[i]+v[ql[i]]+v[q2[i]](買主件和那兩個附件)設(shè)計一個狀態(tài)opt[i]表示花i元錢可買到的物品的價格個重要度最大值。邊界條件是opt[0]=0但是為了區(qū)分花i元錢是否可買到物品我們把初始條件opt[0]:=1;這樣opt[i]>0說明花i元可以買到物品。這樣就不難設(shè)計出這個狀態(tài)的轉(zhuǎn)移方程來：opt[i]=max{opt[i],opt[i-wj]}((i_wj>0)and(opt[i-wj]>0))(0<j<=4)顯然題目的解就是opt[1]到opt[n]中的一個最大值。但在輸出是要注意將解減1。注：價格是10是整數(shù)倍所以讀入數(shù)據(jù)是可以使n=ndiv10,wi=widiv10【源代碼】programbudget;constfin='budget.in';fout='budget.out';maxn=3200;【源代碼】programbudget;constfin='budget.in';fout='budget.out';maxn=3200;maxm=100;varn,m,ans:longint;v,p,q1,q2,q:array[0..maxm]oflongint;opt:array[0..maxn]oflongint;procedureinit;vari,x:longint;beginassign(input,fin);reset(input);assign(output,fout);rewrite(output);readln(n,m);n:=ndiv10;fillchar(q1,sizeof(q1),0);fillchar(q2,sizeof(q2),0);fori:=1tomdobeginreadln(v[i],p[i],q[i]);v[i]:=v[i]div10;q2[q[i]]:=q1[q[i]];q1[q[i]]:=i;end;close(input);end;functionmax(x,y:longint):longint;beginifx>ythenexit(x);exit(y);end;proceduremain;vari,j:longint;beginfillchar(opt,sizeof(opt),0);opt[0]:=1;forj:=1tomdofori:=ndowntov[j]doifq[j]=0thenbeginif(i-v[j]>=0)(opt[i-v[j]]>0)thenandopt[i]:=max(opt[i],opt[i-v[j]]+v[j]*p[j]);if(i-v[j]-v[q1[j]]>=0)and(opt[i-v[j]-v[q1[j]]]>0)thenopt[i]:=max(opt[i],opt[i-v[j]-v[q1[j]]]+v[j]*p[j]+v[q1[j]]*p[q1[j]]);if(i-v[j]-v[q2[j]]>=0)and(opt[i-v[j]-v[q2[j]]]>0)thenopt[i]:=max(opt[i],opt[i-v[j]-v[q2[j]]]+v[j]*p[j]+v[q2[j]]*p[q2[j]]);if(i-v[j]-v[q1[j]]-v[q2[j]]>=0)and(opt[i-v[j]-v[q1[j]]-v[q2[j]]]>0)thenopt[i]:=max(opt[i],opt[i-v[j]-v[q1[j]]-v[q2[j]]]+v[j]*p[j]+v[q1[j]]*p[q1[j]]+v[q2[j]]*p[q2[j]]);ans:=max(ans,opt[i]);end;end;procedureprint;beginwriteln((ans-1)*10);close(output);end;begininit;main;print;end.上面提到的幾個例題都是最基礎(chǔ)的題目，而且把問題抽象后就與背包問題的基本模型一樣了，但有些題目用到了基本模型，要求的解卻不一定很模型一樣，下面看個例子：例題11MoneySystems|(money.pas/c/cpp)來源：USACO2.3【問題描述】母牛們不但創(chuàng)建了他們自己的政府而且選擇了建立了自己的貨幣系統(tǒng)。[Intheirownrebelliousway],，他們對貨幣的數(shù)值感到好奇。傳統(tǒng)地，一個貨幣系統(tǒng)是由1,5,10,20或25,50,和100的單位面值組成的。母牛想知道有多少種不同的方法來用貨幣系統(tǒng)中的貨幣來構(gòu)造一個確定的數(shù)值。舉例來說，使用一個貨幣系統(tǒng){1,2,5,10,...}產(chǎn)生18單位面值的一些可能的方法是:18x1,9x2,8x2+2x1,3x5+2+1，等等其它。寫一個程序來計算有多少種方法用給定的貨幣系統(tǒng)來構(gòu)造一定數(shù)量的面值。保證總數(shù)將會適合longlong(C/C++)和Int64(FreePascal)o【輸入文件】貨幣系統(tǒng)中貨幣的種類數(shù)目是V(1<=V<=25)o要構(gòu)造的數(shù)量錢是N(1<=N<=10,000)o第1行:二整數(shù)，V和N第2行：可用的貨幣V個整數(shù)。【輸出文件】單獨的一行包含那個可能的構(gòu)造的方案數(shù)。【輸入樣例】1025【輸出樣例】10【問題分析】把錢面值，把要構(gòu)造的前看做載重為N的背包，這個問題便是0/1背包的簡化版了，但這個問題和傳

統(tǒng)模型有所差異，不是判斷N是否可構(gòu)成，而是求構(gòu)成N的方案，而且這里的面值是可以重復(fù)利用的（你可以看做是物品有無限多）。對與第一個問題，只要把原來BOOLEAN型的狀態(tài)改為INT64，在遞推過程中累加方案數(shù)即可。對于第二個問題，基本模型中為了避免重復(fù)在內(nèi)重循環(huán)枚舉背包載重時采用倒循環(huán)，現(xiàn)在只要正向循環(huán)就0K了。復(fù)雜度與原模型相同?！驹创a】varopt[0]:=1;{i:longint;fori:=1tovdoID:hhzhaojia2beginforj:=a[i]tondoPROG:moneyassign(input,fin);inc(opt[j],opt[j-a[i]]);LANG:PASCALreset(input);end;}assign(output,fout);procedureprint;programmoney;rewrite(output);beginconstread(v,n);writeln(opt[n]);fin='money.in';fori:=1tovdoclose(output);fout='money.out';read(a[i]);end;maxv=100;close(input);beginmaxn=10010;end;init;varproceduremain;main;a:array[0..maxv]oflongint;varprint;opt:array[0..maxn]ofint64;i,j:longint;end.v,n:longint;beginprocedureinit;背包問題方案的求法：fillchar(opt,sizeof(opt),0);和大多數(shù)DP問題的方案的求法一樣，增加一個數(shù)組path和狀態(tài)維數(shù)相同用來記錄當(dāng)前狀態(tài)的決策就OK了。輸出方案時候通過當(dāng)前決策推出上一決策，這一連穿的決策序列就是要求的方案。下面看這樣一個數(shù)據(jù)：載重：6物品個數(shù)：3重量價值物品1：310物品2：22物品3：19一維狀態(tài)求解過程：i=1:（枚舉物品）opt[0..6]=10011000path[0..6]=0001000｛記錄最后裝入包中的物品的編號｝i=2opt[0..6]=l03110130path[0..6]=0021020i=3opt[0..6]=l10312201322path[0..6]=0323323二維狀態(tài)求解過程：（略）可以看到一維狀態(tài)的最優(yōu)解是正確的，但細心分析發(fā)現(xiàn)一個驚人的問題：方案不對！！什么最優(yōu)解正確而方案不正確呢？因為在解i=3時opt[6]用到的方案數(shù)應(yīng)該是9+2+10=21。顯然這個方案是真確的，所以最優(yōu)解正確。但是求解完opt[6]后，接著求解opt[3]卻把原來的opt[3]=10改成了opt[3]=2+9=ll這樣，在整個求解過程結(jié)束后最后的方案opt[6]=9+2+10就變成了opt[6]=9+2+2+9也就是說1，2兩個物品裝了兩次。這也正是我要說的下面的問題；背包問題一維狀態(tài)于二維狀態(tài)的優(yōu)劣：顯然，一維狀態(tài)的維數(shù)少空間復(fù)雜度低。甚至在一些問題上可以減輕思考負擔(dān)。既然這樣是不是我們就應(yīng)該屏棄二維狀態(tài)解法呢？由于一維狀態(tài)在求解方案是存在錯誤，所以二維狀態(tài)還是很有用啊。當(dāng)然有些問題雖然也是在求解方案但要求方案唯一這樣就又可以用一維狀態(tài)了?？吹竭@里覺得頭暈就上趟廁所，返回來看下面的例題：例題12新年趣事之打牌|來源：vjosP1071【問題描述】過年的時候，大人們最喜歡的活動，就是打牌了。xiaomengxian不會打牌，只好坐在一邊看著。

這天，正當(dāng)一群人打牌打得起勁的時候，突然有人喊道：“這副牌少了幾張！眾人一數(shù)，果然是少了。于是這副牌的主人得意地說：“這是一幅特制的牌，我知道整副牌每一張的重量。只要我們稱一下剩下的牌的總重量，就能知道少了哪些牌了?！贝蠹叶加X得這個辦法不錯，于是稱出剩下的牌的總重量，開始計算少了哪些牌。由于數(shù)據(jù)量比較大，過了不久，大家都算得頭暈了。這時，xiaomengxian大聲說："你們看我的吧！于是他拿出筆記本電腦，編出了一個程序，很快就把缺少的牌找了出來。如果是你遇到了這樣的情況呢？你能辦到同樣的事情嗎？【輸入文件】第一行一個整數(shù)TotalW，表示剩下的牌的總重量。第二行一個整數(shù)N(lvNv=100),表示這副牌有多少張。接下來N行，每行一個整數(shù)Wi(1<=Wi<=1000)，表示每一張牌的重量。【輸出文件】如果無解，則輸出7”；如果有多解，則輸出’-1”；否則，按照升序輸出丟失的牌的編號，相鄰兩個數(shù)之間用一個空格隔開?！据斎霕永?704100110170200【輸出樣例】4【提交鏈接】/Problem_Show.asp?id=1071【問題分析】如果你認真的做了前面的題，把這個題目抽象成背包問題對你來說應(yīng)該易如反掌了，我就不多說了。因為這個問題要求多方案時輸出-1，也就是說要輸出的方案是唯一的，這時你就不需要擔(dān)心一維狀態(tài)的正確性了，可以放心的用一維求解，但要注意只有當(dāng)前狀態(tài)沒有方案是才記錄當(dāng)前的方案，否則會把正確方案替換了?！驹创a1】【源代碼1】programP1071;constmaxw=100010;maxn=110;varpath,opt:array[0..maxw]ofint64;w:array[0..maxn]oflongint;ans:array[0..maxn]ofboolean;n,total:longint;procedureinit;vari:longint;beginread(total);read(n);fori:=1tondoread(w[i]);end;proceduremain;var1.3其它問題i,j:longint;beginfillchar(opt,sizeof(opt),0);fillchar(ans,sizeof(ans),true);opt[0]:=1;fori:=1tondoforj:=totaldowntow[i]doifopt[j-w[i]]>0thenbeginifopt[j]=0thenpath[j]:=i;｛只有當(dāng)前狀態(tài)沒求過才記錄方案｝inc(opt[j],opt[j-w[i]]);end;ifopt[total]=0thenbeginwriteln('O');halt;end;ifopt[total]>1thenbeginwriteln('-1');halt;end;i:=total;whilei>0dobeginans[path[i]]:=false;i:=i-w[path[i]];end;end;procedureprint;vari:longint;beginfori:=1tondoifans[i]thenwrite(i,'');end;begininit;main;print;end.一維動態(tài)規(guī)劃最常見的就是前面總結(jié)的最長下降/非降子序列和0/1背包問題了，當(dāng)然還有別的一寫題。由于不是很常見所以沒有固定的解題模式，到時候具體問題具體分析。下面在看一些例子：例題13挖地雷問題|(P3.pas/c/cpp)來源：N0IP1996(提高組)第三題(有改動)【問題描述】在一個地圖上有N個地窖(Nv=20),每個地窖中埋有一定數(shù)量的地雷。同時，給出地窖之間的連接

路徑。如圖3圖3當(dāng)?shù)亟鸭捌溥B接的數(shù)據(jù)給出之后，某人可以從任一處開始挖地雷，然后可以沿著指出的連接往下挖（僅能選擇一條路徑），當(dāng)無連接時挖地雷工作結(jié)束。設(shè)計一個挖地雷的方案，使某人能挖到最多的地雷?！据斎胛募縉:（表示地窖的個數(shù)）Wl,W2,W3,……WN（表示每個地窖中埋藏的地雷數(shù)量）A12.A1N地窖之間連接路徑（其中Aij=1表示地窖i,jA23..A2N之間是否有通路：通Aij=1,不通Aij==0）AN-1AN（挖地雷的順序）（（挖地雷的順序）（挖地雷的數(shù)量）K1--K2--.KVMAX【輸入樣例】510,8,4,7,6111000011【輸出樣例】->3->4->5max=27【Hint】題目中的路徑是有向的且無環(huán)路（這是我做的改動原題中沒有要求）【問題分析】看到題目的第一影響是貪心以一點出發(fā)找與他連接的地窖中地雷數(shù)最多的一個。但很容易想到反例：512111001100010010按照貪心答案是3,但實際上答案是101。于是就不得不放棄貪心的想法。但是貪心給了我們啟示：從一個頂點出發(fā)要選擇向一個與他相連且以該點出發(fā)可以挖到較多雷的點走。（有點拗口）另一種解釋：如果一個頂點連同n個分量，顯然要則一個較大的就是問題的解答，這個定義是滿足最優(yōu)化原理的。那它滿足無后效性么？因為圖是有向的，所以以與該頂點相連的點在往下走的路線中不包括該點。也就是說圖是一個AOV網(wǎng)（有向無環(huán)圖）。既然滿足最優(yōu)化原理，且無后效性，我們就可以用動態(tài)規(guī)劃解了。這個問題的階段就是拓撲序列，但由于輸入是倒三角形，所以我們沒必要求拓撲序列，只要從N到著求解就可以了。設(shè)計狀態(tài)opt[i]表示以i點出發(fā)可以挖到最多的雷的個數(shù)。狀態(tài)轉(zhuǎn)移方程：opt[i]=max{opt[j]}+w[i]（g[i,j]=1）（g存圖，w[i]存第i個地窖中的雷的個數(shù)）。時間復(fù)雜度：狀態(tài)數(shù)O（n）*轉(zhuǎn)移代價O（n）=O（n2）【源代碼】programP3;constfin='P3.in';fout='P3.out';w,opt,path:array[0..maxn]oflongint;procedureinit;vari,j:longi