noip動(dòng)態(tài)規(guī)劃講解ppt課件-在線瀏覽
2025-06-22 18:15本頁(yè)面
【正文】 For j:=m Downto a[i] Do If f[ja[i]]1 then Begin 00 If f[ja[i]]+b[i]f[j] Then f[j]:=f[ja[i]]+b[i]。 01 If j+s[i,1,1]=m Then If Ff+s[i,1,2]f[j+s[i,1,1]] Then f[j+s[i,1,1]]:=Ff+s[i,1,2]。 11 If j+s[i,1,1]+s[i,2,1]=m Then If Ff+s[i,1,2]+s[i,2,2]f[j+s[i,1,1]+s[i,2,1]] Then f[j+s[i,1,1]+s[i,2,1]]:=Ff+s[i,1,2]+s[i,2,2]。 End。 例如， N=3， K=2，如果面值分別為 1分、 4分，則在 1分～ 6分之間的每一個(gè)郵資值都能得到（當(dāng)然還有 8分、 9分和 12分）；如果面值分別為 1分、3分，則在 1分～ 7分之間的每一個(gè)郵資值都能得到。 【 樣例 】 INPUT N=3 K=2 OUTPUT 1 3 MAX=7 如果你一看到這道題目就想到搜索，那么 這道題目就是搜索。而這個(gè)工作如果要讓枚 C n m 舉來(lái)做，那么太浪費(fèi)資源了。因此我們使用 DP來(lái)枚舉出所有可能的面額，而方法，就是傳說(shuō)中的完全背包（經(jīng)過(guò)處理的）。如下圖所示某人從圖的左上角的 A 點(diǎn)出發(fā)，可以向下行走，也可以向右走，直到到達(dá)右下角的 B點(diǎn)。 此人從 A點(diǎn)到 B 點(diǎn)共走兩次，試找出 2條這樣的路徑，使得取得的數(shù)之和為最大。 現(xiàn)在要做的數(shù)二取方格數(shù)，是否還能像一取方格數(shù)那樣如法炮制呢？ 答案是肯定的！ 我們觀察一下它的路徑。無(wú)論是從 f[i1,j]還是 f[i,j1]走來(lái)，要么是 x坐標(biāo) +1，要么是 y坐標(biāo) +1，總歸 x坐標(biāo)的值 +y坐標(biāo)的值一定比前一個(gè)多 1。 再觀察，我們發(fā)現(xiàn)，走第 n步時(shí)，能走到點(diǎn)是固定的。 因此，走到第 n步時(shí)， x坐標(biāo)和 y坐標(biāo)的和就知道=n+1，這樣我們就不必同時(shí)知道 2條路線 x坐標(biāo)和 y坐標(biāo)了，知道其中一個(gè) t，另外一個(gè)就可以用 n+1t來(lái)表示了。這樣，我們只要枚舉 x， i， j，就能遞推出來(lái)了。 If i=j Then Inc(f[x,i,j],a[i,xi]) Else Begin Inc(f[x,i,j],a[xi,i])。 End。 同樣三取方格數(shù)只要 f[x,i,j,k]用同樣的方法即可。一次素質(zhì)拓展活動(dòng)中，班上同學(xué)安排做成一個(gè) m行 n列的矩陣，而小淵和小軒被安排在矩陣對(duì)角線的兩端，因此，他們就無(wú)法直接交談了。紙條要經(jīng)由許多同學(xué)傳到對(duì)方手里，小淵坐在矩陣的左上角，坐標(biāo) (1,1)，小軒坐在矩陣的右下角，坐標(biāo) (m,n)。 在活動(dòng)進(jìn)行中，小淵希望給小軒傳遞一張紙條，同時(shí)希望小軒給他回復(fù)。反之亦然。小淵和小軒希望盡可能找好心程度高 的同學(xué)來(lái)幫忙傳紙條，即找到來(lái)回兩條傳遞路徑，使得這兩條路徑上同學(xué) 的好心程度只和最大。 Sample Problem7 Sample Problem8 石子歸并原題 【 題目描述 】 在一個(gè)圓形操場(chǎng)的四周擺放著 N堆石子 (N= 100),現(xiàn)要將石子有次序地合并成一堆 .規(guī)定每次只能選取相鄰的兩堆合并成新的一堆 ,并將新的一堆的石子數(shù) ,記為該次合并的得分 .編一程序 ,由文件讀入堆棧數(shù) N及每堆棧的石子數(shù) (=20). 選擇一種合并石子的方案 ,使用權(quán)得做 N－ 1次合并 ,得分的總和最小。 第二行為每堆的石子數(shù) ,每?jī)蓚€(gè)數(shù)之間用一個(gè)空格分隔。 【 輸入 】 4 4 5 9 4 【 輸出 】 22 4 5 9 4 5 9 8 總和： 8 9 13 總和： 21 22 總和： 43 我們用 f[i,j]表示以 i堆石子為開(kāi)頭，以 j堆石子為結(jié)尾的一系列石子歸并起來(lái)的最小總和。所以，f[i,j]這一系列石子必然由 f[i,k]和 f[k+1,j]（ i=kj）這兩堆石子歸并而來(lái)。 因此，狀態(tài)轉(zhuǎn)移方程為： j Σ n=i a[n]。 For i:=1 To n1 Do For j:=1 To 2*ni Do Begin f[j,j+i]:=Maxlongint。 f[j,j+i]:=f[j,j+i]+Sum[j,j+i]。 這樣，求歸并的最大值也是同樣的方法，不再贅述。在項(xiàng)鏈上有 N顆能量珠。并且，對(duì)于相鄰的兩顆珠子，前一顆珠子的尾標(biāo)記一定等于后一顆珠子的頭標(biāo)記。如果前一顆能量珠的頭標(biāo)記為 m，尾標(biāo)記為 r，后一顆能量珠的頭標(biāo)記為 r，尾標(biāo)記為 n，則聚合后釋放的能量為（ Mars單位），新產(chǎn)生的珠子的頭標(biāo)記為 m，尾標(biāo)記為 n。顯然，不同的聚合順序得到的總能量是不同的，請(qǐng)你設(shè)計(jì)一個(gè)聚合順序，使一串項(xiàng)鏈釋放出的總能量最大。我們用記號(hào) ⊕ 表示兩顆珠子的聚合操作， (j⊕ k)表示第 j， k兩顆珠子聚合后所釋放的能量。 這一串項(xiàng)鏈可以得到最優(yōu)值的一個(gè)聚合順序所釋放的總能量為 ((4⊕ 1)⊕ 2)⊕ 3） =10*2*3+10*3*5+10*5*10=710。 【 輸入 】 程序的輸入共有兩行： 第一行共有 2個(gè)自然數(shù) N， K（ 6≤N≤40， 1≤K≤6） 第二行是一個(gè)長(zhǎng)度為 N的數(shù)字串。 【 樣例輸入 】 4 2 1231 【 樣例輸出 】 62 這道題目要求把一個(gè)長(zhǎng)度為 n的數(shù)字串分成 k段，使得每段的乘積最大。 于是狀態(tài)轉(zhuǎn)移方程即可得出： f[i,j]:=Max{f[k,j1]*Number[k+1,i]} (j1=ki) 其中 Number[k+1,j]表示數(shù)字串從第 k+1位到第 i位轉(zhuǎn)換成數(shù)字的值。而諸如最大值最小值之類的變量，一般放入數(shù)組中作為值遞推。該字串 以每行 20個(gè)字母的方式輸入，且保證每行一定為 20個(gè) )。當(dāng)選用一個(gè)單詞之后，其第一個(gè)字母不能再用。單詞在給出 的一個(gè)不超過(guò) 6個(gè)單詞的字典中。 【 樣例輸入 】 3 thisisabook
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1