《noip動態(tài)規(guī)劃講解》ppt課件-文庫吧
2025-04-20 18:15 本頁面
【正文】 大值?！据斎霕永? 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]。 Ff:=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]。 10 If j+s[i,2,1]=m Then If Ff+s[i,2,2]f[j+s[i,2,1]] Then f[j+s[i,2,1]]:=Ff+s[i,2,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。 End。 Sample Problem5 郵票面值設(shè)計（ NOIp1999） 給定一個信封，最多只允許粘貼 N張郵票，計算在給定 K（ N+K≤40）種郵票的情況下（假定所有的郵票數(shù)量都足夠），如何設(shè)計郵票的面值，能得到最大值 MAX，使在 1～ MAX之間的每一個郵資值都能得到。 例如， N=3， K=2，如果面值分別為 1分、 4分，則在 1分～ 6分之間的每一個郵資值都能得到（當然還有 8分、 9分和 12分）；如果面值分別為 1分、3分，則在 1分～ 7分之間的每一個郵資值都能得到?？梢则炞C當 N=3， K=2時， 7分就是可以得到的連續(xù)的郵資最大值，所以 MAX=7，面值分別為 1分、3分。 【 樣例 】 INPUT N=3 K=2 OUTPUT 1 3 MAX=7 如果你一看到這道題目就想到搜索，那么 這道題目就是搜索。那么為什么它出現(xiàn)在動態(tài)規(guī)劃的專題中的？是因為 …… 你 DFS生成一組郵票面值之后，你需要用某種方法把它能達到的面額都枚舉出來。而這個工作如果要讓枚 C n m 舉來做，那么太浪費資源了。枚舉的復雜度是 ，盡管 n、 m很小，但是在大 DFS的前提下就不怎么劃算了。因此我們使用 DP來枚舉出所有可能的面額，而方法，就是傳說中的完全背包（經(jīng)過處理的）。 Sample Problem6 方格取數(shù) （ NOIp2022） 設(shè)有 N*N的方格圖 (N=10,我們將其中的某些方格中填入正整數(shù) ,而其他的方格中則放入數(shù)字 0。如下圖所示某人從圖的左上角的 A 點出發(fā)，可以向下行走，也可以向右走，直到到達右下角的 B點。在走過的路上，他可以取走方格中的數(shù)（取走后的方格中將變?yōu)閿?shù)字 0）。 此人從 A點到 B 點共走兩次，試找出 2條這樣的路徑，使得取得的數(shù)之和為最大。 13+14+4+21+15=67 一取方格數(shù)： f[i,j]:=max{f[i1,j],f[i,j1]}。 現(xiàn)在要做的數(shù)二取方格數(shù)，是否還能像一取方格數(shù)那樣如法炮制呢？ 答案是肯定的！ 我們觀察一下它的路徑。 f[i,j]是從 f[i1,j]或者 f[i,j1]走來。無論是從 f[i1,j]還是 f[i,j1]走來，要么是 x坐標 +1，要么是 y坐標 +1，總歸 x坐標的值 +y坐標的值一定比前一個多 1。 我們來驗證一下： X Y Z X坐標 （ 3， 3） 3+3=6 Y坐標（ 3， 4） 3+4=7 Z坐標（ 4， 4） 4+4=8 X、 Y、Z的坐標和在不斷增加，每次 +1。 再觀察，我們發(fā)現(xiàn)，走第 n步時，能走到點是固定的。觀察其坐標我們發(fā)現(xiàn)，第 n步能走到的點其坐標和為 n1。 因此，走到第 n步時， x坐標和 y坐標的和就知道=n+1，這樣我們就不必同時知道 2條路線 x坐標和 y坐標了，知道其中一個 t，另外一個就可以用 n+1t來表示了。 用 f[x,i,j]表示走到第 x步時，第 1條路線走到橫坐標為 i的地方，第 2條路線走到了橫坐標為 j的地方。這樣，我們只要枚舉 x， i， j，就能遞推出來了。 For x:=3 To m+n Do For i:=1 To Min(x,n) Do For j:=1 To Min(x,n) Do Begin f[x,i,j]:=Max(f[x1,i,j],f[x1,i1,j],f[x1,i,j1],f[x1,i1,j1])。 If i=j Then Inc(f[x,i,j],a[i,xi]) Else Begin Inc(f[x,i,j],a[xi,i])。 Inc(f[x,i,j],a[xj,j])。 End。 End。 同樣三取方格數(shù)只要 f[x,i,j,k]用同樣的方法即可。 傳紙條（ NOIp2022） 【 問題描述 】 小淵和小軒是好朋友也是同班同學，他們在一起總有談不完的話題。一次素質(zhì)拓展活動中，班上同學安排做成一個 m行 n列的矩陣，而小淵和小軒被安排在矩陣對角線的兩端，因此，他們就無法直接交談了。幸運的是，他們可以通過傳紙條來進行交流。紙條要經(jīng)由許多同學傳到對方手里，小淵坐在矩陣的左上角，坐標 (1,1)，小軒坐在矩陣的右下角，坐標 (m,n)。從小淵傳到小軒的紙條只可以向下或者向右傳遞，從小軒傳給小淵的紙條只可以向上或者向左傳遞。 在活動進行中，小淵希望給小軒傳遞一張紙條，同時希望小軒給他回復。班里每個同學都可以幫他們傳遞，但只會幫他們一次，也就是說如果此人在小淵遞給小軒紙條的時候
教學課件相關(guān)推薦
鄂ICP備17016276號-1