1、動態(tài)規(guī)劃,參與競賽的同學(xué)應(yīng)由競爭關(guān)系和獨立關(guān)系（你做你的，我干我的，程序和算法互相保密，彼此津津樂道于對方的失敗和自己的成功）轉(zhuǎn)向合作學(xué)習(xí)的關(guān)系（通過研討算法、集中編程、互測數(shù)據(jù)等互相合作的方式完成學(xué)習(xí)任務(wù)）,2,斐波納契數(shù)列F(n),3,遞歸 vs 動態(tài)規(guī)劃,遞歸版本: F(n) 1if n=0 or n=1 then 2return 1 3else 4return F(n-1) + F(n-2),動態(tài)規(guī)劃: F(n) 1A0 = A1 1 2for i 2 to n do 3Ai Ai-1 + Ai-2 4return An,太慢!,有效率! 算法復(fù)雜度是 O(n),4,方法概要,構(gòu)造一個

2、公式，它表示一個問題的解是與它的子問題的 解相關(guān)的公式.E.g. F(n) = F(n-1) + F(n-2). 為這些子問題做索引 ，以便它們能夠在表中更好的存儲與檢索 (i.e., 數(shù)組array【】) 以自底向上的方法來填寫這表格; 首先填寫最小子問題的解. 這就保證了當(dāng)我們解決一個特殊的子問題時, 可以利用比它更小的所有可利用的 子問題的解.,由于歷史原因, 我們稱這種方法為： 動態(tài)規(guī)劃. 在上世紀(jì)40年代末 (計算機普及很少時),這些規(guī)劃設(shè)計是與”列表“方法相關(guān)的.,5,動態(tài)規(guī)劃算法,算法思想 將待求解的問題分解成若干個子問題，并存儲子問題的解而避免計算重復(fù)的子問題，并由子問題的解得

3、到原問題的解。 動態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題。 動態(tài)規(guī)劃算法的基本要素： 最優(yōu)子結(jié)構(gòu)性質(zhì)和重疊子問題。,原理,6,最優(yōu)子結(jié)構(gòu)性質(zhì)：問題的最優(yōu)解包含著它的子問題的最優(yōu)解。即不管前面的策略如何，此后的決策必須是基于當(dāng)前狀態(tài)（由上一次決策產(chǎn)生）的最優(yōu)決策。 重疊子問題：在用遞歸算法自頂向下解問題時，每次產(chǎn)生的子問題并不總是新問題，有些問題被反復(fù)計算多次。對每個子問題只解一次，然后將其解保存起來，以后再遇到同樣的問題時就可以直接引用，不必重新求解。,原理,7,動態(tài)規(guī)劃,解決問題的基本特征,1. 動態(tài)規(guī)劃一般解決最值（最優(yōu)，最大，最小，最長）問題；,2. 動態(tài)規(guī)劃解決的問題一般是離散的

4、，可以分解（劃分階段）的；,3. 動態(tài)規(guī)劃解決的問題必須包含最優(yōu)子結(jié)構(gòu)，即可以由（n1）的最優(yōu)推導(dǎo)出n的最優(yōu),原理,8,動態(tài)規(guī)劃算法的4個步驟： 1. 刻畫最優(yōu)解的結(jié)構(gòu)特性. （一維，二維，三維數(shù)組） 2. 遞歸的定義最優(yōu)解. （狀態(tài)轉(zhuǎn)移方程） 3. 以自底向上的方法來計算最優(yōu)解. 4. 從計算得到的解來構(gòu)造一個最優(yōu)解.,解決問題的基本步驟,原理,9,實例,例題一. 斐波納契數(shù)列F(n),步驟1：用F（n）表示在斐波納契數(shù)列中第n個數(shù)的值；,步驟2：狀態(tài)轉(zhuǎn)移方程：,步驟3：以自底向上的方法來計算最優(yōu)解,步驟4：在數(shù)組中分析構(gòu)造出問題的解；,10,例題二. 輸入n，求出n！,步驟1：用F（n）表

5、示n！的值；,步驟2：狀態(tài)轉(zhuǎn)移方程：,步驟3：以自底向上的方法來計算最優(yōu)解,實例,11,例題三：排隊買票問題,一場演唱會即將舉行?，F(xiàn)有n個歌迷排隊買票，一個人買一張，而售票處規(guī)定，一個人每次最多只能買兩張票。假設(shè)第i位歌迷買一張票需要時間Ti（1in），隊伍中相鄰的兩位歌迷（第j個人和第j+1個人）也可以由其中一個人買兩張票，而另一位就可以不用排隊了，則這兩位歌迷買兩張票的時間變?yōu)镽j，假如RjTj+Tj+1，這樣做就可以縮短后面歌迷等待的時間，加快整個售票的進程。現(xiàn)給出n, Tj和Rj，求使每個人都買到票的最短時間和方法。,實例,12,1,2,3,4,5,i,i,步驟1：用F（i）表示前i個

6、人買票的最優(yōu)方式，即所需最短時間；現(xiàn)在要決定F(i)需要考慮兩種情況： （1）第i個人的票自己買 （2）第i個人的票由第i-1個人買,步驟2：狀態(tài)轉(zhuǎn)移方程：,min,步驟3：以自底向上的方法來計算最優(yōu)解,13,程序的實現(xiàn),BuyTicks(T, R) 1 n lengthT 2 f0 0 3 f1 T1 4 for i 2 to n do 5 fi fi-2+Ri-1 6 if fi fi-1+Ti then 7 fi fi-1+Ti 8 return f,14,實例,例題四：求最長不降子序列,1問題描述 設(shè)有一個正整數(shù)的序列：b1,b2,，bn，對于下標(biāo)i1i2im，若有bi1bi2bim

7、則稱存在一個長度為m的不下降序列。 例如，下列數(shù)列 13 7 9 16 38 24 37 18 44 19 21 22 63 15 對于下標(biāo)i1=1，i2=4，i3=5，i4=9，i5=13，滿足1316384463,則存在長度為5的不下降序列。 但是，我們看到還存在其他的不下降序列: i1=2，i2=3，i3=4，i4=8，i510，i6=11，i7=12，i8=13，滿足：79161819212263，則存在長度為8的不下降序列。 問題為：當(dāng)b1,b2,，bn給出之后，求出最長的不下降序列。,步驟1：用F（i）表示第i項到最后一項最長不下降序列的長度的值；,步驟2：狀態(tài)轉(zhuǎn)移方程；,di表示

8、數(shù)列中第i項的值；,步驟3：以自底向上的方法來計算最優(yōu)解,15,拓展1： 攔截導(dǎo)彈 （vijos1303）,某國為了防御敵國的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國的導(dǎo)彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。 輸入導(dǎo)彈依次飛來的高度（雷達(dá)給出的高度數(shù)據(jù)是不大于30000的正整數(shù)），計算這套系統(tǒng)最多能攔截多少導(dǎo)彈，如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)。 樣例： INPUT OUTPUT 389 207 155 300

9、 299 170 158 65 6（最多能攔截的導(dǎo)彈數(shù)） 2（要攔截所有導(dǎo)彈最少要配備的系統(tǒng)數(shù)）,16,拓展2：低價購買,“低價購買”這條建議是在奶牛股票市場取得成功的一半規(guī)則。要想被認(rèn)為是偉大的投資者，你必須遵循以下的問題建議:“低價購買；再低價購買”。每次你購買一支股票,你必須用低于你上次購買它的價格購買它。買的次數(shù)越多越好!你的目標(biāo)是在遵循以上建議的前提下，求你最多能購買股票的次數(shù)。你將被給出一段時間內(nèi)一支股票每天的出售價(216范圍內(nèi)的正整數(shù))，你可以選擇在哪些天購買這支股票。每次購買都必須遵循“低價購買；再低價購買”的原則。寫一個程序計算最大購買次數(shù)。 這里是某支股票的價格清單： 日

10、期 1 2 3 4 5 6 7 8 9 10 11 12 價格 68 69 54 64 68 64 70 67 78 62 98 87 最優(yōu)秀的投資者可以購買最多4次股票，可行方案中的一種是： 日期 2 5 6 10 價格 69 68 64 62 輸入 第1行: N (1 = N = 5000)，股票發(fā)行天數(shù) 第2行: N個數(shù)，是每天的股票價格。 輸出 輸出文件僅一行包含兩個數(shù):最大購買次數(shù)和擁有最大購買次數(shù)的方案數(shù)(=231)當(dāng)二種方案“看起來一樣”時（就是說它們構(gòu)成的價格隊列一樣的時候）,這2種方案被認(rèn)為是相同的。,17,拓展3：合唱隊形 （vijis1098）,N位同學(xué)站成一排，音樂老師

11、要請其中的(N-K)位同學(xué)出列，使得剩下的K位同學(xué)排成合唱隊形。 合唱隊形是指這樣的一種隊形：設(shè)K位同學(xué)從左到右依次編號為1，2，K，他們的身高分別為T1，T2，TK， 則他們的身高滿足T1Ti+1TK(1=i=K)。你的任務(wù)是，已知所有N位同學(xué)的身高，計算最少需要幾位同學(xué)出列，可以使得剩下的同學(xué)排成合唱隊形。,輸入的第一行是一個整數(shù)N(2=N=100)，表示同學(xué)的總數(shù)。第一行有n個整數(shù)，用空格分隔，第i個整數(shù)Ti(130=Ti=230)是第i位同學(xué)的身高(厘米)。,輸出包括一行，這一行只包含一個整數(shù)，就是最少需要幾位同學(xué)出列。,樣例輸入 8 186 186 150 200 160 130 1

12、97 220,樣例輸出： 4,18,例題五. 馬攔過河卒,實例,問題描述:如圖，A 點有一個過河卒，需要走到目標(biāo) B 點。卒行走規(guī)則：可以向下、或者向右。同時在棋盤上的任一點有一個對方的馬（如上圖的C點），該馬所在的點和所有跳躍一步可達(dá)的點稱為對方馬的控制點。例如上圖 C 點上的馬可以控制 9 個點（圖中的P1，P2 P8 和 C）。卒不能通過對方馬的控制點。,棋盤用坐標(biāo)表示，A 點（0，0）、B 點（n,m）(n,m 為不超過 20 的整數(shù)，并由鍵盤輸入)，同樣馬的位置坐標(biāo)是需要給出的（約定: CA，同時CB）。現(xiàn)在要求你計算出卒從 A 點能夠到達(dá) B 點的路徑的條數(shù)。 輸入:鍵盤輸入B點的

13、坐標(biāo)（n,m）以及對方馬的坐標(biāo)（X,Y）不用盤錯 輸出:屏幕輸出一個整數(shù)（路徑的條數(shù)）。 輸入輸出樣例:輸入：6 6 3 2輸出：17,19,步驟1：用F（X,Y）表示到棋盤上每個階段(X,Y)的路徑條數(shù)；,步驟2：狀態(tài)轉(zhuǎn)移方程：,步驟3：以自底向上的方法來計算最優(yōu)解,分析：階段：棋盤上的每個可走的點； 每個階段的求解；,F（X,Y）= F (X-1,Y)+ F(X, Y-1) 其中，F(xiàn)（0,0 )=1 F (0,Y)=1 F (X,0)=1,20,例題六：數(shù)字三角形問題,1問題描述 設(shè)有一個三角形的數(shù)塔，頂點結(jié)點稱為根結(jié)點，每個結(jié)點有一個整數(shù)數(shù)值。從頂點出發(fā)，可以向左走，也可以向右走。如圖1

14、0一1所示。,問題：當(dāng)三角形數(shù)塔給出之后，找出一條從第一層到達(dá)底層的路徑，使路徑的值最大。若這樣的路徑存在多條，任意給出一條即可。,21,步驟1,二維數(shù)組 D(X,y)描述問題，D(X,y)表示從頂層到達(dá)第X層第y個位置的最小路徑得分。,步驟2：狀態(tài)轉(zhuǎn)移方程,階段分析：D(1,1)=13 到第x層的第y個位置有兩種可能，要么走右分支 得到，要么走左分支得到。,D(X,y)minD(X-1,y)，D(X-1,y-1+a(X,y) D(1,1)a(1,1),22,拓展：棧（vijos 1122）,【問題背景】棧是計算機中經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，簡單的說，棧就是限制在一端進行插入刪除操作的線性表。 棧有兩種

15、最重要的操作，即pop（從棧頂彈出一個元素）和push（將一個元素進棧）。,寧寧考慮的是這樣一個問題：一個操作數(shù)序列，從1，2，一直到n（圖示為1到3的情況），棧A的深度大于n。 現(xiàn)在可以進行兩種操作， 1.將一個數(shù)，從操作數(shù)序列的頭端移到棧的頭端（對應(yīng)數(shù)據(jù)結(jié)構(gòu)棧的push操作） 2. 將一個數(shù)，從棧的頭端移到輸出序列的尾端（對應(yīng)數(shù)據(jù)結(jié)構(gòu)棧的pop操作）,23,使用這兩種操作，由一個操作數(shù)序列就可以得到一系列的輸出序列，下圖所示為由1 2 3生成序列2 3 1的過程。（原始狀態(tài)如上圖所示）,24,你的程序?qū)o定的n，計算并輸出由操作數(shù)序列1，2，n經(jīng)過操作可能得到的輸出序列的總數(shù)。 【輸入格

16、式】 輸入文件只含一個整數(shù)n（1n18） 【輸出格式】 輸出文件只有一行，即可能輸出序列的總數(shù)目 【輸入樣例】 3 【輸出樣例】 5,25,例題七：最長公共子序列,一個給定序列的子序列是在該序列中刪去若干元素后得到的序列。 給定兩個序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。 最長公共子序列:公共子序列中長度最長的子序列。 最長公共子序列問題 給定兩個序列X=x1,x2,xm和Y=y1,y2, yn，找出X和Y的一個最長公共子序列。 例如: X = (A, B, C, B, D, A, B) X的子序列: 所有X的子集(集合中元素按原來在X中的順序排列

17、) (A, B, D), (B, C, D, B), 等等.,26,例子,X = (A, B, C, B, D, A, B) X = (A, B, C, B, D, A, B) Y = (B, D, C, A, B, A) Y = (B, D, C, A, B, A) (B, C, B, A)和(B, D, A, B)都是X和Y 的最長公共子序列(長度為4) 但是,(B, C, A)就不是X和Y的最長公共子序列,27,窮舉法,對于每一個Xm的子序列,驗證它是否是Yn的子序列. Xm有2m個子序列 每個子序列需要o(n)的時間來驗證它是否是Yn的子序列. 從Yn的第一個字母開始掃描下去,如果不是

18、則從第二個開始 運行時間: o(n2m),28,給定一個序列Xm = (x1, x2, , xm),我們定義Xm的第i個前綴為: Xi = ( x1, x2, , xi ) i = 0, 1, 2, , m ci, j為序列Xi = (x1, x2, , xi)和Yj = (y1, y2, , yj)的最長公共子序列的長度.,分析:,最優(yōu)子結(jié)構(gòu)性質(zhì)： 設(shè)序列Xm=x1,x2,xm和Yn=y1,y2,yn的一個最長公共子序列為Zk=z1,z2,zk，則 1.若xm=yn，則zk=xm=yn，且Zk-1是Xm-1和Yn-1的最長公共子序列。 2.若xmyn，且zkxm，則Zk是Xm-1和Yn的最長

19、公共子序列。 3.若xmyn，且zk yn ，則Zk是Xm和Yn-1的最長公共子序列。,步驟1,步驟2,29,狀態(tài)轉(zhuǎn)移方程,yj:,xm,y1,y2,yn,x1,x2,xi,i,0,1,2,n,m,1,2,0,步驟3,30,附加信息,yj:,D,A,C,F,A,B,xi,j,i,0,1,2,n,m,1,2,0,矩陣 bi, j: 它告訴我們要獲得最優(yōu)結(jié)果應(yīng)該如何選擇 如果 xi = yj bi, j = 1 如果 ci - 1, j ci, j-1 bi, j = 2 否則 bi, j = 3,3,3,C,D,31,LCS-LENGTH(X, Y, m, n) 1 for i 1 to m d

20、o ci, 0 0 2 for j 0 to n do c0, j 0 3 for i 1 to m do 4 for j 1 to n do 5 if xi = yj 6 then ci, j ci - 1, j - 1 + 1 7 bi, j “” 8 else if ci - 1, j ci, j - 1 9 then ci, j ci - 1, j 10 bi, j “” 11 else ci, j ci, j - 1 12 bi, j “” 13 return c and b,運行時間: (nm),32,例子,X = (B, D, C, A, B, A) Y = (A, B, C,

21、B, D, A,B),0,1,2,6,3,4,5,yj,B,D,A,C,A,B,5,1,2,0,3,4,6,7,D,A,B,xi,C,B,A,B, 0, 0, 0,1,1,1, 1,2,33,找出最長共同子序列,PRINT-LCS(b, X, i, j) 1 if i = 0 or j = 0 2 then return 3 if bi, j = 4 then PRINT-LCS(b, X, i - 1, j - 1) 5 print xi 6 elseif bi, j = 7 then PRINT-LCS(b, X, i - 1, j) 8 else PRINT-LCS(b, X, i, j

22、 - 1),34,例題8：0-1背包問題,小偷有一個可承受W的背包 有n件物品: 第i個物品價值vi 且重wi 目標(biāo): 找到xi使得對于所有的xi = 0, 1, i = 1, 2, ., n wixi W 并且 xivi 最大,部分背包問題,35,最優(yōu)子結(jié)構(gòu),考慮最多重W的物品且價值最高 如果我們把j物品從背包中拿出來 剩下的裝載一定是取自n-1個物品使得不超過載重量W wj并且所裝物品價值最高的裝載,36,0-1背包問題的動態(tài)規(guī)劃,對于每一個物品i，都有兩種情況需要考慮 第1種情況:物品i的重量wiw,即小偷不拿物品i P(i, w) = P(i - 1, w),步驟1,P(i, w) 考

23、慮前i件物品所能獲得的最高價值,其中w是背包的承受力,步驟2,階段分析：,37,Knapsack (S,W) 1 for w 0 to w1 - 1 do P1, w 0; 2 for w w1 to W do P1, w v1; 3 for i 2 to n do 4 for w 0 to W do 5 if wi w then 6 Pi,w Pi-1, w; 7 else 8 Pi,w maxPi-1, w, Pi-1,w-wi + vi,運行時間: (nW),38,0-1背包問題的動態(tài)規(guī)劃,0:,n,1,w - wi,W,i-1,0,P(i, w) = max vi + P(i - 1,

24、 w-wi), P(i - 1, w) ,帶走物品i,不帶走物品i,i,w,39,P(i, w) = max vi + P(i - 1, w-wi), P(i - 1, w) ,W = 5,0,12,12,12,12,10,12,22,22,22,10,12,22,30,32,10,15,25,30,37,w,i,40,構(gòu)造最優(yōu)解法,0,1,2,3,4,5,1,2,3,4,0,12,12,12,12,10,12,22,22,22,10,12,22,30,32,10,15,25,30,37,0,從 P(n, W)開始 當(dāng)往左上走物品i被帶走 當(dāng)直往上走物品i未被帶走,41,子問題的重復(fù),0:,n

25、,1,W,i-1,0,P(i, w) = max vi + P(i - 1, w-wi), P(i - 1, w) ,i,w,例如: 所有用灰色表示的子問題都取決于P(i-1, w),子問題的重復(fù),1,0,0,1,0,1,10,8,10,8,6,8,10,0,6,2,8,2,8,6,10,0,1,6,2,3,8,2,3,8,1,6,5,10,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,例子: n=5, p=6,3,5,4,6, w=2,2,6,5,4, W=10,43,拓展1：裝箱問題 （vijos 1133）,有一個箱子容量為v(正整數(shù)，ov20000

26、)，同時有n個物品(on30)，每個物品有一個體積 (正整數(shù))。要求從 n 個物品中，任取若千個裝入箱內(nèi)，使箱子的剩余空間為最小。,輸入格式 Input Format,第一行，一個整數(shù)，表示箱子容量；第二行，一個整數(shù)，表示有n個物品；接下來n行，分別表示這n個物品的各自體積。,輸出格式 Output Format,一個整數(shù)，表示箱子剩余空間。,樣例輸入 Sample Input,24 6 8 3 12 7 9 7,樣例輸出 Sample Output,0,44,拓展2：采藥 (vijos1104),辰辰是個天資聰穎的孩子，他的夢想是成為世界上最偉大的醫(yī)師。為此，他想拜附近最有威望的醫(yī)師為師。醫(yī)

27、師為了判斷他的資質(zhì)，給他出了一個難題。醫(yī)師把他帶到一個到處都是草藥的山洞里對他說：“孩子，這個山洞里有一些不同的草藥，采每一株都需要一些時間，每一株也有它自身的價值。我會給你一段時間，在這段時間里，你可以采到一些草藥。如果你是一個聰明的孩子，你應(yīng)該可以讓采到的草藥的總價值最大?！?如果你是辰辰，你能完成這個任務(wù)嗎？,輸入格式 Input Format,輸入的第一行有兩個整數(shù)T（1 = T = 1000）和M（1 = M = 100），用一個空格隔開，T代表總共能夠用來采藥的時間，M代表山洞里的草藥的數(shù)目。接下來的M行每行包括兩個在1到100之間（包括1和100）的整數(shù)，分別表示采摘某株草藥的時

28、間和這株草藥的價值。,輸出格式 Output Format,輸出包括一行，這一行只包含一個整數(shù)，表示在規(guī)定的時間內(nèi)，可以采到的草藥的最大總價值。,樣例輸入 Sample Input,70 3 71 100 69 1 1 2,樣例輸出 Sample Output,3,45,拓展3：開心的金明 （vijos 1317）,金明今天很開心，家里購置的新房就要領(lǐng)鑰匙了，新房里有一間他自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說：“你的房間需要購買哪些物品，怎么布置，你說了算，只要不超過N 元錢就行”。今天一早金明就開始做預(yù)算，但是他想買的東西太多了，肯定會超過媽媽限定的N 元。于是，他把每件物

29、品規(guī)定了一個重要度，分為5 等：用整數(shù)15 表示，第5 等最重要。他還從因特網(wǎng)上查到了每件物品的價格（都是整數(shù)元）。他希望在不超過N 元（可以等于N 元）的前提下，使每件物品的價格與重要度的乘積的總和最大。設(shè)第j 件物品的價格為vj，重要度為wj，共選中了k 件物品，編號依次為j1.jk，則所求的總和為：vj1*wj1+.+vjk*wjk請你幫助金明設(shè)計一個滿足要求的購物單.,輸入格式 Input Format,輸入的第1 行，為兩個正整數(shù)，用一個空格隔開：N m（其中N（30000）表示總錢數(shù)，m(25)為希望購買物品的個數(shù)。）從第2 行到第m+1 行，第j 行給出了編號為j-1的物品的基本

30、數(shù)據(jù)，每行有2 個非負(fù)整數(shù)v p（其中v 表示該物品的價格（v10000），p 表示該物品的重要度（15）,46,輸出格式 Output Format,輸出只有一個正整數(shù)，為不超過總錢數(shù)的物品的價格與重要度乘積的總和的最大值（100000000）,樣例輸入 Sample Input,1000 5 800 2 400 5 300 5 400 3 200 2,樣例輸出 Sample Output,3900,47,拓展4：金明的預(yù)算方案 (vijos 1313 ),金明今天很開心，家里購置的新房就要領(lǐng)鑰匙了，新房里有一間金明自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說：“你的房間需要購買哪

31、些物品，怎么布置，你說了算，只要不超過N元錢就行”。今天一早，金明就開始做預(yù)算了，他把想買的物品分為兩類：主件與附件，附件是從屬于某個主件的，下表就是一些主件與附件的例子：主件 附件電腦 打印機，掃描儀書柜 圖書書桌 臺燈，文具工作椅 無如果要買歸類為附件的物品，必須先買該附件所屬的主件。每個主件可以有0個、1個或2個附件。附件不再有從屬于自己的附件。金明想買的東西很多，肯定會超過媽媽限定的N元。于是，他把每件物品規(guī)定了一個重要度，分為5等：用整數(shù)15表示，第5等最重要。他還從因特網(wǎng)上查到了每件物品的價格（都是10元的整數(shù)倍）。他希望在不超過N元（可以等于N元）的前提下，使每件物品的價格與重要

32、度的乘積的總和最大。設(shè)第j件物品的價格為vj，重要度為wj，共選中了k件物品，編號依次為j1，j2，jk，則所求的總和為：vj1*wj1+vj2*wj2+ +vjk*wjk。（其中*為乘號）請你幫助金明設(shè)計一個滿足要求的購物單。,48,輸入格式 Input Format,輸入文件的第1行，為兩個正整數(shù)，用一個空格隔開：N m 其中N（0，表示該物品為附件，q是所屬主件的編號）,輸出格式 Output Format,輸出文件只有一個正整數(shù)，為不超過總錢數(shù)的物品的價格與重要度乘積的總和的最大值（200000）。,樣例輸入 Sample Input,1000 5 800 2 0 400 5 1 30

33、0 5 1 400 3 0 500 2 0,樣例輸出 Sample Output,2200,49,例題9：石子歸并,描述：在一個圓形操場的四周擺放著N堆石子(N=100),現(xiàn)要將石子有次序地合并成一堆.規(guī)定每次只能選取相鄰的兩堆合并成新的一堆,并將新的一堆的石子數(shù),記為該次合并的得分.編一程序,由文件讀入堆棧數(shù)N及每堆棧的石子數(shù)(=20).(!)選擇一種合并石子的方案,使用權(quán)得做N1次合并,得分的總和最小;(2)選擇一種合并石子的方案,使用權(quán)得做N1次合并,得分的總和最小;,輸入數(shù)據(jù):第一行為石子堆數(shù)N;第二行為每堆的石子數(shù),每兩個數(shù)之間用一個空格分隔.輸出數(shù)據(jù):從第一至第N行為得分最小的合并

34、方案.第N+1行是空行.從第N+2行到第2N+1行是得分最大合并方案.每種合并方案用N行表示,其中第i行(1=i=N)表示第i次合并前各堆的石子數(shù)(依順時針次序輸出,哪一堆先輸出均可).要求將待合并的兩堆石子數(shù)以相應(yīng)的負(fù)數(shù)表示.輸入輸出范例:,輸入:44594輸出:最小43 最大54,50,輸入:44594輸出: ,拓：輸出合并的方案：,51,用i，j表示一個從第i堆數(shù)起，順時針數(shù)j堆時的子序列第i堆、第i堆、第（ij1）mod n堆,步驟1,fi，j將子序列i，j中的j堆石子合并成一堆的最佳得分和；（結(jié)果數(shù)組） ci，j將i，j一分為二，其中子序列的堆數(shù)；（記錄分隔點）,打印合并方案時使用,

35、52,顯然，對每一堆石子來說，它的fi， ci， （iN）對于子序列i，j來說，若求最小得分總和，fi，j的初始值為； 若求最大得分總和，fi，j的初始值為。（iN，jN）。規(guī)劃的方向是順推。先考慮含二堆石子的N個子序列（各子序列分別從第堆、第堆、第N堆數(shù)起，順時針數(shù)堆）的合并方案f，f，fN，c，c，cN，然后考慮含三堆石子的個子序列（各子序列分別從第堆、第堆、第堆數(shù)起，順時針數(shù)堆）的合并方案f，f，fN，c，c，cN，依次類推，直至考慮了含N堆石子的N個子序列（各子序列分別從第堆、第堆、 、第N堆數(shù)起，順時針數(shù)N堆）的合并方案f，N，f，N，fN，Nc，N，c，N，cN，N最后，在子序列，

36、N，N，N，N中，選擇得分總和（f值）最?。ɑ蜃畲螅┑囊粋€子序列i，N（iN），由此出發(fā)倒推合并過程。,階段分析：,53,例如對（圖624）中的堆石子，按動態(tài)規(guī)劃方程順推最小得分和。 依次得出含二堆石子的個子序列的合并方案f， f， f ， c， c， c，f， f， f，c， c， c，含三堆石子的個子序列的合并方案f， f， f， c， c， c，f， f， f，c， c， c，含四堆石子的個子序列的合并方案f， f， f，c， c， c，f， f， f，c， c， c，,例題： ,54,步驟2：狀態(tài)轉(zhuǎn)移方程,ci，jk fi，jfi，kfx，j-kt （，）,55,附加信息：打印合并方案,56,拓展1：能量項鏈 （vijos 1312）,在Mars星球上，每個Mars人都隨身佩帶著一串能量項鏈。在項鏈上有N顆能量珠。能量珠是一顆有頭標(biāo)記與尾標(biāo)記的珠子，這些標(biāo)記對應(yīng)著某個正整數(shù)。并且，對于相鄰的兩顆珠子，前一顆珠子的尾標(biāo)記一定等于后一顆珠子的頭標(biāo)記。因為只有這樣，通過吸盤（吸盤是Mars人吸收能量的一種器官）的作用，這兩顆珠子才能