noip動(dòng)態(tài)規(guī)劃講解ppt課件-文庫吧在線文庫
【正文】 動(dòng)態(tài)規(guī)劃 (dynamic programming)是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過程最優(yōu)化的數(shù)學(xué)方法。如上例中 3，18， 23， 24就是一個(gè)長度為 4的不下降序列，同時(shí)也有 3， 7， 10， 12， 16， 24長度為 6的不下降序列。 【 輸出文件 】 輸出文件包括一行 ， 這一行只包含一個(gè)整數(shù) ， 就是最少需要幾位同學(xué)出列 。 求解將哪些物品裝入背包可使價(jià)值總和最大。如果要買歸類為附件的物品，必須先買該附件所屬的主件。（ 其中 *為乘號(hào)） 請(qǐng)你幫助金明設(shè)計(jì)一個(gè)滿足要求的購物單。 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]。而這個(gè)工作如果要讓枚 C n m 舉來做，那么太浪費(fèi)資源了。 現(xiàn)在要做的數(shù)二取方格數(shù)，是否還能像一取方格數(shù)那樣如法炮制呢？ 答案是肯定的！ 我們觀察一下它的路徑。這樣，我們只要枚舉 x， i， j，就能遞推出來了。一次素質(zhì)拓展活動(dòng)中，班上同學(xué)安排做成一個(gè) m行 n列的矩陣，而小淵和小軒被安排在矩陣對(duì)角線的兩端，因此，他們就無法直接交談了。小淵和小軒希望盡可能找好心程度高 的同學(xué)來幫忙傳紙條，即找到來回兩條傳遞路徑，使得這兩條路徑上同學(xué) 的好心程度只和最大。所以，f[i,j]這一系列石子必然由 f[i,k]和 f[k+1,j]（ i=kj）這兩堆石子歸并而來。 這樣，求歸并的最大值也是同樣的方法，不再贅述。顯然，不同的聚合順序得到的總能量是不同的，請(qǐng)你設(shè)計(jì)一個(gè)聚合順序，使一串項(xiàng)鏈釋放出的總能量最大。 【 樣例輸入 】 4 2 1231 【 樣例輸出 】 62 這道題目要求把一個(gè)長度為 n的數(shù)字串分成 k段，使得每段的乘積最大。當(dāng)選用一個(gè)單詞之后，其第一個(gè)字母不能再用。之后的任務(wù)就是求單詞數(shù)了。 帥帥想請(qǐng)你幫忙寫個(gè)程序，對(duì)于任意矩陣，可以求出取數(shù)后的最大得分。在橋上有一些石子，青蛙很討厭踩在這些石子上。 【 輸入文件 】 第一行一個(gè)正整數(shù) L（ 1 = L = 10^9），表示獨(dú)木橋的長度。 L最大有 10^9，第一個(gè) For就已經(jīng)無法承受龐大的時(shí)間限制和空間限制了。那么我們用原始的方法做就會(huì)浪費(fèi)很大的資源。 這種方法叫狀態(tài)壓縮，我們這題用的方法叫離散 化。 【 樣例 】 輸入： 7 3 輸出： 4 {四種分法為： 1， 1， 5； 1， 2， 4； 1， 3， 3； 2， 2， 3； } 應(yīng)該明確這是一道數(shù)學(xué)題，數(shù)學(xué)題往往有明顯或暗藏的規(guī)律可以快速求得解。 這樣 ， f[10,4]就被改成了 f[6,2]、 f[6,3]、 f[6,4]等小狀態(tài)。所以我們要精益求精：這題還有 O(n*k)的方法。 試求一棵符合中序遍歷為（ 1,2,3,…, n） 且加分最高的二叉樹 tree。 總結(jié)： 動(dòng)態(tài)規(guī)劃是 NOIp中的一類大問題，它在聯(lián)賽中考的幾率是 99%。同樣的如果 j是 a[1]~a[i1]這棵子樹的根，那么 a[1]~a[j1]就是左子樹中的左子樹，a[j+1]~a[i1]就是左子樹中的右子樹，依次類推。 這樣，遞推就成了 n*k的了 For i:=1 To n Do For j:=1 To k Do If i=j Then f[i,j]:=f[i1,j1]+f[ij,j]。 知道了遞推公式，我們就可以推得 f[n,k]。 根據(jù)前面講的，有幾個(gè)枚舉量我們就設(shè)幾個(gè)狀態(tài)，這道題目明顯 n和 k都是枚舉量，要求的幾種方案是值，因此建立起遞推狀態(tài)： f[i,j]表示將 i分成 j份的方案數(shù)。 1， 5， 1。最壞情況就是 s=9， t=10了（仔細(xì)想想為什么？）。 第二種情況： st 我們先來看一組數(shù)據(jù)。 【 輸出文件 】 一個(gè)整數(shù)，表示青蛙過河最少需要踩到的石子數(shù)。一次跳躍的距離是 S到 T之間的任意正整數(shù)（包括 S,T）。 把 一段的頭和尾看做一堆石子，把 a[i]*2^(m+1i)看做每次歸并的加分，每次歸并不是取相鄰的，而是取一段中的頭或尾 —— 就是石子歸并。最終 f[1,4]=f[1,3]+1。 【 樣例輸入 】 3 thisisabookyouareaoh 4 is a ok sab 【 樣例輸出 】 7 this / isabookyoua / reaoh 看到這道題目應(yīng)該馬上有這種意識(shí)了：和乘積最大神似！ 所以本題除了求出 i~j之間有多少單詞以外基本上就沒什么難度了。而諸如最大值最小值之類的變量，一般放入數(shù)組中作為值遞推。 這一串項(xiàng)鏈可以得到最優(yōu)值的一個(gè)聚合順序所釋放的總能量為 ((4⊕ 1)⊕ 2)⊕ 3） =10*2*3+10*3*5+10*5*10=710。并且，對(duì)于相鄰的兩顆珠子，前一顆珠子的尾標(biāo)記一定等于后一顆珠子的頭標(biāo)記。 For i:=1 To n1 Do For j:=1 To 2*ni Do Begin f[j,j+i]:=Maxlongint。 第二行為每堆的石子數(shù) ,每兩個(gè)數(shù)之間用一個(gè)空格分隔。 在活動(dòng)進(jìn)行中，小淵希望給小軒傳遞一張紙條，同時(shí)希望小軒給他回復(fù)。 End。 再觀察，我們發(fā)現(xiàn)，走第 n步時(shí)，能走到點(diǎn)是固定的。如下圖所示某人從圖的左上角的 A 點(diǎn)出發(fā)，可以向下行走，也可以向右走，直到到達(dá)右下角的 B點(diǎn)。 例如， N=3， K=2，如果面值分別為 1分、 4分，則在 1分～ 6分之間的每一個(gè)郵資值都能得到（當(dāng)然還有 8分、 9分和 12分）；如果面值分別為 1分、3分，則在 1分～ 7分之間的每一個(gè)郵資值都能得到。【輸入樣例】 1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0 【輸出樣例】 2200 For i:=1 To n Do 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]。于是，他把每件物品規(guī)定了一個(gè)重要
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1