1、動態規劃的有關講解（詳細！）狀態是一維的我用這題的思想來為大家入個門。下降/非降子序列問題：問題描述：挖掘題目的本質，一但抽象成這樣的描述就可以用這個方法解在一個無序的序列a1,a2,a3,a4an里，找到一個最長的序列滿足：ai=aj=ak=am,且 ijkajakam, 且ijkm.（最長下降子序列）。PS：如果前i-1個數中用到ak （akai或akai（或 aj=ai），optj+1就是opti的值；用方程表示為： opti=max（optj）+1（0=ji 且 aj=ai）最長非降子序列opti=max（optj）+1（0=jai）最長下降子序列實現求解的部分代碼：opt0:=max

2、size； maxsize 為 maxlongint 或-maxlongintfor i:=1 to n do （這里是從頭到尾，當然也可以從尾到頭，可以這樣表示for i:=n downto1 do）for j:=0 to i-1 do（上面如果是從尾到頭，那么這里可以for j:=i+1 to n do）if （ ajai） and （optj+1opti） thenopti:=optj+1;ans:=-maxlongint;for i:=1 to n doif optians then ans:=opti;ans 為最終解復雜度：從上面的實現不難看出時間復雜度為O（N2），空間復雜度O（

3、N）；攔截導彈（missile.pas/c/cpp）來源：NOIP1999（提高組）第一題【問題描述】某國為了防御敵國的導彈襲擊，發展出一種導彈攔截系統。但是這種導彈攔截系統有一個缺陷：雖然它的第一發炮彈能夠到達任意 的高度，但是以后每一發炮彈都不能高于前一發的高度。某天，雷達捕捉到敵國的導彈來襲。由于該系統還在試用階段，所以只有一套 系統，因此有可能不能攔截所有的導彈。輸入導彈依次飛來的高度（雷達給出的高度數據是不大于30000的正整數），計算這套系統最多能攔截多少導彈，如果要攔截所有 導彈最少要配備多少套這種導彈攔截系統。【輸入文件】missile.in單獨一行列出導彈依次飛來的高度。【輸

4、出文件】missile.out兩行，分別是最多能攔截的導彈數，要攔截所有導彈最少要配備的系統數 【輸入樣例】389 207 155 300 299 170 158 65【輸出樣例】62PS :這道題的第一問我們不難想到就是求最長下降子序列。所以這題我們可以使用動態規劃來實現。以導彈依次飛來的順序為階段，設計狀態opti表示前i個導彈中攔截了導彈i可以攔截最多能攔截到的導彈的個數。 狀態轉移方程：opti=max(optj)+1 (hi=hj,0=j=ai) and (optj+1opti) thenopti:=optj+1;anslen:=0;for i:=1 to n doif optian

5、slen thenanslen:=opti;fillchar(opt,sizeof(opt),0);a0:=-maxlongint;for i:=1 to n dofor j:=i-1 downto 0 doif (ajopti) thenopti:=optj+1;anstime:=0;for i:=1 to n doif optianstime thenanstime:=opti;end;procedure print;beginwriteln(anslen);writeln(anstime);close(input);close(output);end;begininit;main;pri

6、nt;end.合唱隊形(chorus.pas/c/cpp)來源：NOIP2004(提高組)第一題N位同學站成一排，音樂老師要請其中的(N-K)位同學出列，使得剩下的K位同學排成合唱隊形。合唱隊形是指這樣的一種隊形：設K位同學從左到右依次編號為1，2，K，他們的身高分別為T1，T2,，TK，則他們的身 高滿足 T1.Ti+1TK(1=i=K)。你的任務是，已知所有N位同學的身高，計算最少需要幾位同學出列，可以使得剩下的同學排成合唱隊形。【輸入文件】輸入文件chorus.in的第一行是一個整數N(2=N=100)，表示同學的總數。第一行有n個整數，用空格分隔，第i個整數 Ti(130=Ti=230

7、)是第i位同學的身高(厘米)。【輸出文件】輸出文件chorus.out包括一行，這一行只包含一個整數，就是最少需要幾位同學出列。【樣例輸入】8186 186 150 200 160 130 197 220【樣例輸出】4【數據規模】對于50%的數據，保證有n=20；對于全部的數據，保證有n=100。PS :所謂的合唱隊隊形就是中間最高然后依次從兩邊遞減。題目要求出隊人數最少，于是我們可以抽象的想象成從左到最高的人是最長 上升子序列，從最高人的人到右邊是最長下降子序列。我們來看一下復雜度：如果采用枚舉中間人的話，計算最長上升或下降子序列復雜度O (M2)一共求N次，所以復雜度變為O (M3)。這個

8、復雜度對這題的數據已經可以解決，但不是最優的方法。其實最長上升或下降子序列只要一次就可以了，因為最長最長上升或下降子序列不受中間人的影響。只要用OPT1求一次最長上升子序 列，OPT2求一次最長下降子序列。這樣答案就是N-max(opt1i+opt2i-1). (i是從1到n)。這樣我們就把復雜度從O (M3 )降到了 O (M2)。參考程序：program chorus;const maxn=200;varopt1,opt2,a:array0.maxn of longint;n,ans:longint;procedure init;vari:longint;beginassign(input

9、, chorus.out);reset(input);assign(output, chorus.in);rewrite(output);readln(n);for i:=1 to n doread(ai);end;procedure main;vari,j:longint;begina0:=-maxlongint;for i:=1 to n dofor j:=i-1 downto 0 doif (ajopt1i) then opt1i:=opt1j+1;an+1:=-maxlongint;for i:=n downto 1 dofor j:=i+1 to n+1 doif (ajopt2i)

10、 then opt2i:=opt2j+1;ans:=0;for i:=1 to n doif opt1i+opt2ians thenans:=opt1i+opt2i;end;procedure print;beginwriteln(n-ans+1);close(input);close(output);end;begininit;main;print;end.（ships.pas/c/cpp）來源：奧賽經典（提高篇）【問題描述】PALMIA國家被一條河流分成南北兩岸，南北兩岸上各有N個村莊。北岸的每一個村莊有一個唯一的朋友在南岸，且他們的朋友村莊 彼此不同。每一對朋友村莊想要一條船來連接他們，

11、他們向政府提出申請以獲得批準。由于河面上常常有霧，政府決定禁止船只航線相交（如果相 交，則很可能導致碰船）。你的任務是編寫一個程序，幫助政府官員決定批準哪些船只航線，使得不相交的航線數目最大。【輸入文件】ships.in輸入文件由幾組數據組成。每組數據的第一行有2個整數X，Y，中間有一個空格隔開，X代表PALMIA河的長度（10=X=6000）， Y代表河的寬度（10=Y=100）。第二行包含整數N，表示分別坐落在南北兩岸上的村莊的數目（1=N=5000）。在接下來的N行 中，每一行有兩個非負整數C，D，由一個空格隔開，分別表示這一對朋友村莊沿河岸與PALMIA河最西邊界的距離（C代表北岸的村

12、 莊，D代表南岸的村莊），不存在同岸又同位置的村莊。最后一組數據的下面僅有一行，是兩個0，也被一空格隔開。【輸出文件】ships.out對輸入文件的每一組數據，輸出文件應在連續的行中表示出最大可能滿足上述條件的航線的數目。【輸入樣例】30 4722 42 610 315 129 817 174 20 0【輸出樣例】4PS :這道題目相對來說思考難度較高，從字面意義上看不出問題的本質來，有點無法下手的感覺。這里我給大家推薦兩種思考這類問題 的方法。法一：尋找規律法（我前面總結提到的第3個方法）尋找規律自然要推幾組數據，首先當然有從樣例入手；仔細觀察上圖：紅色航線是合法的，那么他們滿足什么規律呢?

13、北岸紅線的端點：49南岸紅線的端點：28C1 C2 C3 C415171217D1 D2 D3 D4不難看出無論線的斜率如何，都有這樣的規律:C1C2C3C4 且 D1D2D3D4如果我們把輸入數據排升序，問題變抽象為：在一個序列（D）里找到最長的序列滿足DIDJDk且ijk這樣的話便是典型的最長非降子序列問題了。法二：邊界條件法（我前面總結提到的第4個方法）邊界法其實就是把數據往小了縮，顯然N=1是答案是1。N=2時呢?考慮這樣一組數據：N=2C1 D1C2 D2當C1D2那么一定會相交，反之則不會相交。當C1C2時，如果D1D2那么一定會相交，反之則不會相交。N=3C1 D1C2 D2C3

14、 D3其實不用在推導N=3 了，有興趣的可以推導去。看N=2時就能得出：對于任意兩條航線如果滿足CiCj且DiDj則兩條航線不相交。這樣的話要想在一個序列里讓所有的航線都不相交那比然滿足， C1C2C3Cans且D1D2D3Dans，也就是將C排序后求出最長的滿足這個條件的序列的長度就是解。這樣分析后顯然是一個最長非降子序列問題復雜度：排序可以用O(nlogn)的算法，求最長非降子序列時間復雜度是O(M2).總復雜度為O(M2)。參考程序：program ships;constmaxn=5010;typeretype=recordC,D:longint;end;varx,y,n,ans:lon

15、gint;a:array0.maxn of retype;opt:array0.maxn of longint;procedure init;vari:longint;beginreadln(n);for i:=1 to n doread(ai.c,ai.d);end;procedure quick(L,r:longint);vari,j,x:longint;y:retype;begini:=L;j:=r;x:=a(i+j) div 2.c;repeatwhile ai.cx dodec；if ij;if jL then quick(L,j);if ir then quick(i,r);end

16、;procedure main;vari,j:longint;beginfillchar(opt,sizeof(opt),0);quick(1,n);for i:=1 to n dofor j:=0 to i-1 doif (aj.dopti) then opti:=optj+1;ans:=-maxlongint;for i:=1 to n doif ansopti thenans:=opti;writeln(ans);end;beginassign(input,ships.in);reset(input);assign(output,ships.out);rewrite(output);re

17、ad(x,y);while (x+y0) dobegininit;main;read(x,y);end;close(input);close(output);end.背包問題我參考了背包九講等資料作出了如下整理。首先說說背包問題的基本模型：現有N個物品，每個物品的價值為V,重量為W。求用一個載重量為S的背包裝這寫物品，使得所裝物品的總價值最高。背包問題用貪心和搜索解，當然效果不佳，不過在我的貪心和搜索總結中會說到。顯然標準的解法是動態規化，我在解決這個問題時習 慣設計一維狀態，還可以設計二維的，二維狀態在下面會講，現在只討論用一維狀態實現背包問題。背包問題的分類：（1）小數背包:物品的重量是實

18、數，如油，水等可以取1.67升（2）整數背包：部分背包：所選物品可以是一部分。0/1背包：每個物品只能選一次，或不選。不能只選一部分（3）多重背包：背包不只一個。部分背包：同小數背包。0/1背包：這個問題是最經常出現的問題，應該熟練掌握。我們先看一下0/1背包的簡化版：現有N個物品，每個物品重量為W，這些物品能否使在載重量為S的背包裝滿（即重量和正好為S）？如過不能那能使物品重量和最 重達到多少？針對這一問題我們以物品的個數分階段，設計一個狀態opti表示載重量為i的背包可否裝滿，顯然opti的基類型是booleano決策是什么呢？當要裝第i個物品時，如果前i-1個物品可以使載重為k的背包裝滿

19、，那么載重為k+wi的背包就可以裝滿。于是對于一個optj來說， 只要optj-wi是true （表示可裝滿）那optj就可以裝滿，但要注意：針對每一個物品枚舉背包的載重量時如果這樣正向的推導會使同 一個物品用好幾次，因為k+wi可裝滿那k+wi+wi就可裝滿，但實際上是裝不滿的因為物品只有一個。解決這個問題很簡單，只要逆 向推導就OK 了。這樣劃分階段，設計狀態，滿足無后效性和么？顯然對與一個每一個階段都是獨立的，物品的順序并不影響求解，因為裝物品的次序不限。而對于optj只考慮optj-wi而不考慮后面 的，所以滿足無后效性。有了上面的分析不難寫出狀態轉移方程：optj:=optj-w1

20、（optj-wi=true時間復雜度：階段數O（S）*狀態數（O（N）*轉移代價（O（1）=O（SN）像裝箱，采藥等問題都是背包問題轉變過來的。在將轉移方程化為實際代碼時，一共可以有3種寫法，到時我會一一列舉，讓大家 開闊思路。裝箱問題（pack.pas/c/cpp）來源：NOIP2001（普及組）第四題【問題描述】有一個箱子容量為V （正整數，0=V=20000），同時有n個物品（0n=30=，每個物品有一個體積（正整數）。要求n個物品中，任取若干個裝入箱內，使箱子的剩余空間為最小。【輸入文件】第一行一個正整數V表示箱子的容量，第二行一個正整數N表示物品個數，接下來N行列出這N個物品各自的體

21、積。【輸出文件】單獨一行，表示箱子最小的剩余空間。【輸入樣例】2468312797【輸出樣例】PS：本題是經典的0/1背包問題，并且是0/1背包的簡化版，把箱子看做背包，容量看做載重量，體積看做重量，剩余空間最小也就是 盡量裝滿背包。于是這個問題便成了：有一個栽重量為V的背包，有N個物品，盡量多裝物品，使背包盡量的重。設計一個狀態opti表示重量i可否構成。狀態轉移方程：optj:=optj-wi (optj-wi=true最終的解就是 v-x(x0)and(optj-wi+wi=optj) then optj :=optj-wi+wi;(最后V背包能裝的最大容量是optv-1,因為一開始op

22、t0:=1)。3、這是另一種整數數組來表示該方程代碼。opt0:=0;for i:=1 to n dofor j:=v downto wi doif (optj-wi+wi=optj) then optj :=optj-wi+wi;(最后V背包能裝的最大容量為optv)。這里大家會覺得2和3是一樣的，其實如果大家跟蹤的話就會發現，第2種比第3種好，為什么呢？因為第2種的替換率比第3種少， 也就是說一旦數據過大的話第2種比第3種更優。參考程序：program pack;constmaxv=20010;maxn=100;varopt:array0.maxv of boolean;w:array0.

23、maxn of longint;v,n,x:longint;procedure init;vari:longint;beginassign(input, pack.in);reset(input);assign(output, pack.out);rewrite(output);read(v);read(n);for i:=1 to n doread(wi);end;procedure main;vari,j:longint;beginfillchar(opt,sizeof(opt),false);opt0:=true;for i:=1 to n dofor j:=v downto wi do

24、if optj-wi then optj :=true;x:=v;while not optx do dec(x);end;procedure print;beginwriteln(v-x);close(input);close(output);end;begininit;main;print;end.砝碼稱重來源：NOIP1996 (提高組)第四題【問題描述】設有1g、2g、3g、5g、10g、20g的砝碼各若干枚(其總重=1000),用他們能稱出的重量的種類數。【輸入文件】a1 a2 a3 a4 a5 a6(表示1g砝碼有a1個，2g砝碼有a2個，20g砝碼有a6個，中間有空格)。【輸出文

25、件】Total=N(N表示用這些砝碼能稱出的不同重量的個數，但不包括一個砝碼也不用的情況)。【輸入樣例】1 0 0 0 0【輸出樣例】TOTAL=3PS :把問題稍做一個改動，已知a1+a2+a3+a4+a5+a6個砝碼的重量wi, wi G 1,2,3,5,10,20其中砝碼重量可以相等，求用這些砝碼可 稱出的不同重量的個數。這樣一改就是經典的0/1背包問題的簡化版了，求解方法完全和上面說的一樣，這里就不多說了，只是要注意這個題目不是求最大載重 量，是統計所有的可稱出的重量的個數。參考程序：program P4;constmaxn=1010;w:array1.6 of longint=(1,

26、2,3,5,10,20);var opt:array0.maxn of boolean;a:array1.6 of longint;procedure init;vari:longint;beginfor i:=1 to 6 doread(ai);end;procedure main;vari,j,k:longint;beginfillchar(opt,sizeof(opt),false);opt0:=true;for i:=1 to 6 dofor j:=1 to ai dofor k:=maxn downto wi doif optk-wi then optk:=true;end;proc

27、edure print;varans,i:longint;beginans:=0;for i:=1 to maxn doif opti theninc(ans);writeln(ans);end;begininit;main;print;end.積木城堡來源：vijos P1059【問題描述】XC的兒子小XC最喜歡玩的游戲用積木壘漂亮的城堡。城堡是用一些立方體的積木壘成的，城堡的每一層是一塊積木。小XC是 一個比他爸爸XC還聰明的孩子，他發現壘城堡的時候，如果下面的積木比上面的積木大，那么城堡便不容易倒。所以他在壘城堡的時 候總是遵循這樣的規則。小XC想把自己壘的城堡送給幼兒園里漂亮的女孩子們

28、，這樣可以增加他的好感度。為了公平起見，他決定把送給每個女孩子一樣 高的城堡，這樣可以避免女孩子們為了獲得更漂亮的城堡而引起爭執。可是他發現自己在壘城堡的時候并沒有預先考慮到這一點。所以 他現在要改造城堡。由于他沒有多余的積木了，他靈機一動，想出了一個巧妙的改造方案。他決定從每一個城堡中挪去一些積木，使得 最終每座城堡都一樣高。為了使他的城堡更雄偉，他覺得應該使最后的城堡都盡可能的高。任務：請你幫助小XC編一個程序，根據他壘的所有城堡的信息，決定應該移去哪些積木才能獲得最佳的效果。【輸入文件】第一行是一個整數N(N0 dobegininc(top);atop:=m;inc(tothig,m);

29、read(m);end;for i:=1 to top dofor j:=tothig downto 1 doif (j-ai=0) and (optii,j-ai) thenoptii,j:=true;end;ans:=maxhig;while not opt1,ans dodec(ans);while not can(ans) dodec(ans);writeln(ans);end;begininit;main;end.階段總結回顧上面的內容充分說明動態規劃的本質就是遞推。其實按照我的理解(動規涉及最優決策，遞推是單純的總結)背包問題的簡 化版更準確點算是遞推而非動態規劃，至于動歸和遞推之

30、間的界線本來就很模糊(至少我這么認為)把它看做什么都可以，沒必要咬文 嚼字。回到0/1背包的原問題上(如果你忘了就去上面看看)。如果在不知道這個模型的情況下我們怎么做這個題呢？這就要用到第一節提到的方法二：三要素法題目中明確說明對于一個物品要不就拿走要不就放下，其實題目赤裸裸的告訴我們決策就是不拿(用0表示)或拿(用1表示)。這樣 想都不用想就知道了決策，這也是本題的突破口。知道了決策寫個搜索的程序應該是很輕松的了。那么階段是什么呢顯然，給你一堆東西讓你往包里塞，你當然是一個一個的那來，塞進去。那么階段很明顯就是物品的個數。狀態又是什么呢有的人在裝東西是有個習慣(比如說我)就是先把東西分類，然

31、后把同類的東西打個小包，最后在把小包放進去，我們可以按這個思想 給物品打一些小包，也就是按照單位為1的遞增的順序準備好多小包，比如載重是6的包，可以為它準備載重是1，2, 3, 4, 5的小包。 這樣狀態就可以想出來了：設計狀態opti，j表示裝第i個物品時載重為j的包可以裝到的最大價值。opti-1,j(j-wi0)狀態轉移方程：opti,j= maxopti-1,j,opti-1,j-wi+vi (j-wi=0,i0)(wi:第i個物品的重量，vi第i個物品的價值)解釋：要載重為j的背包空出wi(j-wi)的空間且裝上第i個物品，比不裝獲得的價值大就裝上它。邊界條件：opt0,i=0;(沱

32、1.S)注：這種二維的狀態表示應該在下節講，但是為了方便理解先在這里說了。上面的方法動態規劃三要素都很明顯，實現也很簡單。但是在我初學背包時卻用另外一種一維的狀態表示法。用第一節說的思考方法五(放寬約束和增加約束)在重新思考一下這個問題：怎么放寬約束呢把題目中的價值去掉，不考慮價值即最優就變成背包問題的簡化版了。那簡化版的求解對我們有何啟示呢？ 再一次增加約束：背包只能裝滿。顯然對于N個裝滿背包的方案中只要找到一個價值最大的就是問題的解。那么裝不滿怎么辦呢？其實裝不滿背包，它總要達到一定的 重量(X)。我們可以把這種情況看作是裝滿一個載重為X的小包。總結一下上面的思維過程：放寬約束讓我們找到問

33、題的突破口和背包問題簡化版一樣，我們可以卻定載重為S的背包是否可以裝滿。增加約束讓我們找到問題的求解方法一一在裝滿背包的方案中選擇最優的一個方案。這樣問題就解決了。設計一個狀態optj表示裝滿載重為j的背包可獲得的最大價值。對于第i個物品，只要optj-wi可以裝滿且optj-wi+vi比optj大 就裝上這個物品(更新optj)。怎么使optj既有是否構成又有最優的概念呢？optj只表示最優，只不過使初始條件+1，判斷optj是否為0，如果optj=0說明j裝不滿。邊界條件：opt0=1;狀態轉移方程：optj=maxoptj-wi (0in,wi=j=S)問題解：ans=maxopti-1

34、(0i=s)時間復雜度：階段數O(S)*狀態數(O(N) *轉移代價(O(1) =O (SN)采藥(medic.pas/c/cpp)來源：NOIP2005 (普及組)第三題【問題描述】辰辰是個天資聰穎的孩子，他的夢想是成為世界上最偉大的醫師。為此，他想拜附近最有威望的醫師為師。醫師為了判斷他的資質， 給他出了一個難題。醫師把他帶到一個到處都是草藥的山洞里對他說：“孩子，這個山洞里有一些不同的草藥，采每一株都需要一些時 間，每一株也有它自身的價值。我會給你一段時間，在這段時間里，你可以采到一些草藥。如果你是一個聰明的孩子，你應該可以讓采 到的草藥的總價值最大。”如果你是辰辰，你能完成這個任務嗎？

35、【輸入文件】輸入文件medic.in的第一行有兩個整數T (1 = T = 1000)和M (1 = M = 100)，用一個空格隔開，T代表總共能夠用來采藥 的時間，M代表山洞里的草藥的數目。接下來的M行每行包括兩個在1U100之間(包括1和100)的整數，分別表示采摘某株草藥 的時間和這株草藥的價值。【輸出文件】輸出文件medic.out包括一行，這一行只包含一個整數，表示在規定的時間內，可以采到的草藥的最大總價值。【輸入樣例】310069 11 2【輸出樣例】3【數據規模】對于30%的數據，M = 10；對于全部的數據，M y then max:=xelse max:=y;end;pro

36、cedure main;varj:longint;beginfillchar(opt,sizeof(opt),0);for i:=1 to n dofor j:=1 to t doif j-wi0) and (optj-wi+vioptj) thenoptj:=optj-wi+vi;ans:=-maxlongint;for i:=1 to t doif optians then ans:=opti;end;procedure print;beginwriteln(ans-1);close(output);end;begininit;main;print;end.開心的金明來源：NOIP2006

37、 (普及組)第二題【問題描述】金明今天很開心，家里購置的新房就要領鑰匙了，新房里有一間他自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說: “你的房間需要購買哪些物品，怎么布置，你說了算，只要不超過N元錢就行”。今天一早金明就開始做預算，但是他想買的東西太 多了，肯定會超過媽媽限定的N元。于是，他把每件物品規定了一個重要度，分為5等：用整數15表示，第5等最重要。他還從 因特網上查到了每件物品的價格(都是整數元)。他希望在不超過N元(可以等于N元)的前提下，使每件物品的價格與重要度的乘 積的總和最大。設第j件物品的價格為vj，重要度為wj，共選中了 k件物品，編號依次為j1.jk，則所求

38、的總和為： vj1*wj1+.+vjk*wjk 請你幫助金明設計一個滿足要求的購物單.【輸入文件】輸入的第1行，為兩個正整數，用一個空格隔開：N m(其中N(30000)表示總錢數，m(25)為希望購買物品的個數。)從第2行到第m+1行，第j行給出了編號為j-1的物品的基本數據，每行有2個非負整數v p(其中v表示該物品的價格(vW10000)，p表示該物品的重要度(15)【輸出文件】輸出只有一個正整數，為不超過總錢數的物品的價格與重要度乘積的總和的最大值(=0) and (optj-vi0) and (optj-vi+vi*pioptj)then optj:=optj-vi+vi*pi;en

39、d;end;end;procedure print;vari,ans:longint;beginans:=0;for i:=1 to n doif optians thenans:=opti;writeln(ans-1);end;begininit;main;print;end.金明的預算方案(budget.pas/c/cpp)來源：NOIP2006第二題【問題描述】金明今天很開心，家里購置的新房就要領鑰匙了，新房里有一間金明自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說：“你 的房間需要購買哪些物品，怎么布置，你說了算，只要不超過N元錢就行”。今天一早，金明就開始做預算了，他把想買的

40、物品分為 兩類：主件與附件，附件是從屬于某個主件的，下表就是一些主件與附件的例子： 主件附件電腦打印機，掃描儀書柜圖書書桌臺燈，文具工作椅 無如果要買歸類為附件的物品，必須先買該附件所屬的主件。每個主件可以有0個、1個或2個附件。附件不再有從屬于自己的附件。金 明想買的東西很多，肯定會超過媽媽限定的N元。于是，他把每件物品規定了一個重要度，分為5等：用整數15表示，第5等最重 要。他還從因特網上查到了每件物品的價格(都是10元的整數倍)。他希望在不超過N元(可以等于N元)的前提下，使每件物品的 價格與重要度的乘積的總和最大。設第j件物品的價格為vj，重要度為wj，共選中了 k件物品，編號依次為

41、j1，j2,，jk，則所求的總和為： vj1*wj1+vj2*wj2+ +vjk*wjk。(其中 *為乘號) 請你幫助金明設計一個滿足要求的購物單。【輸入文件】輸入文件budget.in的第1行，為兩個正整數，用一個空格隔開：N m(其中N (32000)表示總錢數，m (60)為希望購買物品的個數。)從第2行到第m+1行，第j行給出了編號為j-1的物品的基本數據，每行有3個非負整數：v p q(其中v表示該物品的價格(v0，表示該物品為附件，q是所屬主件的編號)【輸出文件】輸出文件budget.out只有一個正整數，為不超過總錢數的物品的價格與重要度乘積的總和的最大值(=0)and(fj-a

42、i.v0+ai.w0fj) then fj:=fj-ai.v0+ai.w0; if (j-ai.v0-ai.v1=0)and(fj-ai.v0-ai.v1+ai.w0+ai.w1fj) then fj:=fj-ai.v0-ai.v1+ai.w0+ai.w1;if (j-ai.v0-ai.v2=0)and(fj-ai.v0-ai.v2+ai.w0+ai.w2fj) then fj:=fj-ai.v0-ai.v2+ai.w0+ai.w2; if (j-ai.v0-ai.v1-ai.v2=0)and(fj-ai.v0-ai.v1-ai.v2+ai.w0+ai.w1+ai.w2fj) then fj:

43、=fj-ai.v0-ai.v1-ai.v2+ai.w0+ai.w1+ai.w2; end;max:=0;for i:=1 to n do if fimax then max:=fi;writeln(max*10);end.背包問題方案的求法和大多數DP問題的方案的求法一樣，增加一個數組path和狀態維數相同用來記錄當前狀態的決策就OK 了。 輸出方案時候通過當前決策推出上一決策，這一連穿的決策序列就是要求的方案。下面看這樣一個數據：載重：6物品個數：3重量價值物品1：310物品2：22物品3：19一維狀態求解過程：i=1 :（枚舉物品）opt0.6= 1 0 0 11 0 0 0path0.6

44、=0 0 0 10 0 0 記錄最后裝入包中的物品的編號i=2opt0.6=1 0 3 11 0 13 0path0.6=0 0 2 1 0 20i=3opt0.6=1 10 3 12 20 13 22path0.6=0 3 2 3323二維狀態求解過程：（略）可以看到一維狀態的最優解是正確的，但細心分析發現一個驚人的問題：方案不對！什么最優解正確而方案不正確呢？因為在解i=3時opt6用到的方案數應該是9+2+10=21。顯然這個方案是真確的，所以最優解正確。但是求解完opt6后，接著求解opt3 卻把原來的opt3=10改成了 opt3=2+9=11這樣，在整個求解過程結束后最后的方案op

45、t6=9+2+10就變成了 opt6=9+2+2+9也就是說 1，2兩個物品裝了兩次。這也正是我要說的下面的問題；背包問題一維狀態于二維狀態的優劣：顯然，一維狀態的維數少空間復雜度低。甚至在一些問題上可以減輕思考負擔。既然這樣是不是我們就應該屏棄二維狀態解法呢？由于一維狀態在求解方案是存在錯誤，所以二維狀態還是很有用啊。當然有些問題雖然也是在求解方案但要求方案唯一這樣就又可以用 一維狀態了。Money Systems（money.pas/c/cpp）來源：USACO 2.3【問題描述】母牛們不但創建了他們自己的政府而且選擇了建立了自己的貨幣系統。In their own rebellious

46、way,他們對貨幣的數值感到好奇。 傳統地，一個貨幣系統是由1,5,10,20或25,50,和100的單位面值組成的。母牛想知道有多少種不同的方法來用貨幣系統中的貨幣來構造一個確定的數值。舉例來說，使用一個貨幣系統1,2,5,10,.產生18單位面值的一些可能的方法是:18x1, 9x2, 8x2+2x1, 3x5+2+1，等等其它。寫一個程序來 計算有多少種方法用給定的貨幣系統來構造一定數量的面值。保證總數將會適合long long (C/C+)和Int64 (Free Pascal)。【輸入文件】貨幣系統中貨幣的種類數目是V (1= V=25)。要構造的數量錢是N (1= N=10,000

47、)。第1行：二整數，V和N第2行：可用的貨幣V個整數。【輸出文件】單獨的一行包含那個可能的構造的方案數。【輸入樣例】3 101 2 5【輸出樣例】10PS：把錢面值，把要構造的前看做載重為N的背包，這個問題便是0/1背包的簡化版了，但這個問題和傳統模型有所差異，不是判斷N 是否可構成，而是求構成N的方案，而且這里的面值是可以重復利用的(你可以看做是物品有無限多)。對與第一個問題，只要把原來BOOLEAN型的狀態改為INT64，在遞推過程中累加方案數即可。對于第二個問題，基本模型中為了避免重復在內重循環枚舉背包載重時采用倒循環，現在只要正向循環就OK了。還有一種理解就是 optn=optn-1+

48、optn-2“.1、opt0:=1;for i:=1 to v dofor j:=ai to n doinc(optj,optj-ai);2、opt0:=1;for i:=1 to n do beginx:=0;for j:=1 to v doinc(x,opti-aj);opti:=x;end;參考程序：program money;constmaxv=100;maxn=10010;vara:array0.maxv of longint;opt:array0.maxn of int64;v,n:longint;procedure init;vari:longint;beginassign(in

49、put, money.in);reset(input);assign(output, money.out);rewrite(output);read(v,n);for i:= 1 to v doread(ai);close(input);end;procedure main;vari,j:longint;beginfillchar(opt,sizeof(opt),0);opt0:=1;for i:=1 to v dofor j:=ai to n doinc(optj,optj-ai);end;procedure print;beginwriteln(optn);close(output);en

50、d;begininit;main;print;end.新年趣事之打牌來源：vijos P1071【問題描述】過年的時候，大人們最喜歡的活動，就是打牌了。xiaomengxian不會打牌，只好坐在一邊看著。這天，正當一群人打牌打得起勁的時候，突然有人喊道：“這副牌少了幾張！”眾人一數，果然是少了。于是這副牌的主人得意地 說：“這是一幅特制的牌，我知道整副牌每一張的重量。只要我們稱一下剩下的牌的總重量，就能知道少了哪些牌了。”大家都覺得這 個辦法不錯，于是稱出剩下的牌的總重量，開始計算少了哪些牌。由于數據量比較大，過了不久，大家都算得頭暈了。這時，xiaomengxian大聲說：“你們看我的吧！

51、”于是他拿出筆記本電腦，編出了一個程序，很快就把缺少的牌找了出來。如果是你遇到了這樣的情況呢？你能辦到同樣的事情嗎？【輸入文件】第一行一個整數TotalW，表示剩下的牌的總重量。第二行一個整數N(1N=100)，表示這副牌有多少張。接下來N行，每行一個整數Wi(1=Wi0 thenbeginif optj=0 thenpathj:=i;只有當前狀態沒求過才記錄方案inc(optj,optj-wi);end;if opttotal=0 thenbeginwriteln(0);halt;end;if opttotal1 thenbeginwriteln(-1);halt;end;i:=total;

52、while i0 dobeginanspathi:=false;i:=i-wpathi;end;end;procedure print;vari:longint;beginfor i:=1 to n doif ansi then write（i,）;end;begininit;main;print;end.挖地雷問題（P3.pas/c/cpp）來源：NOIP1996 （提高組）第三題（有改動）【問題描述】在一個地圖上有N個地窖（Nopti) thenbeginopti:=optj;pathi:=j;end;inc(opti,wi);end;ans:=1;for i:=2 to n doif o

53、ptioptans then ans:=i;end;procedure print;vari:longint;beginwrite(ans);i:=pathans;while i0 dobeginwrite(-,i);i:=pathi;end;writeln;writeln(max=,optans);close(output);end;begininit;main;print;end.r勵一一曲 .Party Lamps在IOI98的節日宴會上，我們有N(10=N=0)的燈。例如：1,4,7.一個計數器C記錄按鈕被按下的次數。當宴會開始，所有的燈都亮著，此時計數器C為0。你將得到計數器C(0=

54、C=10000)上的數值和經過若干操作后所有燈的狀態。寫一個程序去找出所有燈最后可能的與所給出信息相符的 狀態，并且沒有重復。PROGRAM NAME: lampsINPUT FORMAT不會有燈會在輸入中出現兩次。第一行:N。第二行:C最后顯示的數值。第三行：最后亮著的燈，用一個空格分開，以-1為結束。第四行：最后關著的燈，用一個空格分開，以-1為結束。SAMPLE INPUT (file lamps.in)101-17 -1在這個樣例中，有10盞燈，只有1個按鈕被按下。最后7號燈是關著的。OUTPUT FORMAT每一行是所有燈可能的最后狀態(沒有重復)。每一行有N個字符，第1個字符表示1

55、號燈，最后一個字符表示N號燈。0表示關閉，1 表示亮著。這些行必須從小到大排列(看作是二進制數)。如果沒有可能的狀態，則輸出一行IMPOSSIBLE。SAMPLE OUTPUT (file lamps.out)000000000001010101010110110110在這個樣例中，有三種可能的狀態：所有燈都關著1,4,7,10 號燈關著，2,3,5,6,8,9 亮著。1,3,5,7,9 號燈關著，2, 4, 6, 8, 10 亮著。Compiling.Compile: OKExecuting.Test 1: TEST OK 0.000 secs, 208 KBTest 2: TEST OK

56、0.000 secs, 208 KBTest 3: TEST OK 0.000 secs, 212 KBTest 4: TEST OK 0.000 secs, 212 KBTest 5: TEST OK 0.000 secs, 208 KBTest 6: TEST OK 0.000 secs, 212 KBTest 7: TEST OK 0.000 secs, 212 KBTest 8: TEST OK 0.000 secs, 208 KBAll tests OK.PS:注意模擬。ID:bemaula1PROB:lampsLANG:PASCALprogram Paryt_Lamps;var l

57、ight:array1.16of string;off,on:array1.100of integer;kind:array1.16,1.4of integer;a:array1.4of integer;flag:boolean;r,l,m,n,c,k,p:longint;procedure init;var k:integer;begin readln(n); readln(c);m:=c;r:=0;read(k);while k-1 dobegininc(r);onr:=k;read(k);end;readln;l:=0;read(k);while k-1 dobegininc(l);of

58、fl:=k;read(k);end;readln;end;procedure dfs(t:longint);var i,j:longint;beginif (t=4)or(m=0)thenbegina4:=m mod 2;inc(k);for j:=1 to 4 dokindk,j:=aj end;if (t0)thenfor i:=0 to 1 dobeginat:=i;m:=m-i;dfs(t+1);m:=m+i;at:=0;end;end;procedure check;var try:array1.100of boolean;i,j:longint;beginfor i:=1 to k

59、 dobeginfillchar(try,sizeof(try),1);if kindi,1=1 then for j:=1 to n do tryj:=not tryj;if kindi,2=1 then for j:=1 to n do if j mod 2=1 then tryj:=not tryj;if kindi,3=1 then for j:=1 to n do if j mod 2=0 then tryj:=not tryj;j:=0;if kindi,4=1 thenwhile j*3+1=n dobegintryj*3+1:=not tryj*3+1;inc(j);end;f

60、lag:=true;for j:=1 to r do if not tryonj then begin flag:=false; break; end;if flag thenfor j:=1 to l do if tryoffj then begin flag:=false; break; end;if flag thenbegininc(p);for j:=1 to n doif tryj then lightp:=lightp+1else lightp:=lightp+0;end;end;end;procedure qsort(l,r:longint);var i,j:longint;m