【正文】 NOIp2022） 【 問題描述 】 小淵和小軒是好朋友也是同班同學(xué)，他們在一起總有談不完的話題。 Inc(f[x,i,j],a[xj,j])。 用 f[x,i,j]表示走到第 x步時，第 1條路線走到橫坐標為 i的地方，第 2條路線走到了橫坐標為 j的地方。 我們來驗證一下： 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。 13+14+4+21+15=67 一取方格數(shù)： f[i,j]:=max{f[i1,j],f[i,j1]}。 Sample Problem6 方格取數(shù) （ NOIp2022） 設(shè)有 N*N的方格圖 (N=10,我們將其中的某些方格中填入正整數(shù) ,而其他的方格中則放入數(shù)字 0。那么為什么它出現(xiàn)在動態(tài)規(guī)劃的專題中的？是因為 …… 你 DFS生成一組郵票面值之后，你需要用某種方法把它能達到的面額都枚舉出來。 Sample Problem5 郵票面值設(shè)計（ NOIp1999） 給定一個信封，最多只允許粘貼 N張郵票，計算在給定 K（ N+K≤40）種郵票的情況下（假定所有的郵票數(shù)量都足夠），如何設(shè)計郵票的面值，能得到最大值 MAX，使在 1～ MAX之間的每一個郵資值都能得到。 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]。如果 q=0， 表示該物品為主件，如果 q0， 表示該物品為附件， q是所屬主件的編號） 【輸出文件】 只有一個正整數(shù)，為不超過總錢數(shù)的物品的價格與重要度乘積的總和的最大值。 設(shè)第 j件物品的價格為 v[j]， 重要度為 w[j]， 共選中了 k件物品，編號依次為 j1，j2， …… ， jk， 則所求的總和為： v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk] 。金明想買的東西很多，肯定會超過媽媽限定的 N元。今天一早，金明就開始做預(yù)算了，他把想買的物品分為兩類：主件與附件，附件是從屬于某個主件的。 求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。第 i件物品的費用是 c[i]， 價值是 w[i]。 某天 ， 雷達捕捉到敵國的導(dǎo)彈來襲 。 第一行有 n個整數(shù) ， 用空格分隔 ， 第 i個整數(shù) Ti(130=Ti=230)是第 i位同學(xué)的身高 。 合唱隊形 （ NOIp2022） 【 問題描述 】 N位同學(xué)站成一排 ， 音樂老師要請其中的 (NK)位同學(xué)出列 ， 使得剩下的 K位同學(xué)排成合唱隊形 。 若存在 i1i2i3 … ie 且有 a(i1)a(i2) … a(ie)則稱為長度為 e的不下降序列。 動態(tài)規(guī)劃是信息學(xué)競賽中選手必須熟練掌握的一種算法 ,它以其多元性廣受出題者的喜愛。動態(tài)規(guī)劃算法把多階段過程轉(zhuǎn)化為一系列單階段問題，利用各階段之間的關(guān)系，逐個求解，以得到全局最優(yōu)策略。 動態(tài)規(guī)劃實質(zhì)： 枚舉 + 遞推 狀態(tài) 狀態(tài)轉(zhuǎn)移方程 Sample Problem1 1 3 5 9 1 從樹的根到樹的葉節(jié)點，最多能取多少數(shù)？ 貪心 ： 答案錯誤 暴力搜索 ： 如果數(shù)據(jù)大會超時 我們先將 NOIp里的動態(tài)規(guī)劃分分類： 最長不降子序列 背包 方格取數(shù) 石子歸并 狀態(tài)壓縮 數(shù)學(xué)遞推 順序遞推 設(shè)有由 n個不相同的整數(shù)組成的數(shù)列，記為 : a(1)、 a(2)、 …… 、 a(n)且 a(i)a(j) (i， j=n) 例如 3， 18， 7， 14， 10， 12， 23， 41， 16， 24。 For i:=1 To n Do For j:=1 To i1 Do If (a[i]=a[j])And(f[i]f[j]+1) Then f[i]:=f[j]+1。 【 輸入文件 】 輸入文件第一行是一個整數(shù) N(2=N=100)， 表示同學(xué)的總數(shù) 。 但是這種導(dǎo)彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達任意的高度 ， 但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度 。 樣例： INPUT OUTPUT 389 207 155 300 299 170 158 65 6（ 最多能攔截的導(dǎo)彈數(shù) ） 2（ 要攔截所有導(dǎo)彈最少要配備的系統(tǒng)數(shù) ） Sample Problem3 反例： 9 8 7 1 10 6 5 4 9 8 7 1 10 6 5 4 9 8 7 1 10 6 5 1 10 1 10 10 9 8 7 1 10 6 5 4 1 10 10 6 5 4 01背包： 有 N件物品和一個容量為 V的背包。第 i種物品的費用是 c[i]， 價值是w[i]。更讓他高興的是，媽媽昨天對他說：“你的房間需要購買哪些物品，怎么布置，你說了算，只要不超過 N元錢就行”。附件不再有從屬于自己的附件。他希望在不超過 N元（可以等于 N元）的前提下，使每件物品的價格與重要度的乘積的總和最大。）從第 2行到第 m+1行，第 j行給出了編號為 j1的物品的基本數(shù)據(jù)，每行有 3個非負整數(shù) v p q（ 其中 v表示該物品的價格（ v10000）， p表示該物品的重要度（ 1~5）， q表示該物品是主件還是附件。 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]。 End。 【 樣例 】 INPUT N=3 K=2 OUTPUT 1 3 MAX=7 如果你一看到這道題目就想到搜索，那么 這道題目就是搜索。因此我們使用 DP來枚舉出所有可能的面額，而方法，就是傳說中的完全背包（經(jīng)過處理的）。 此人從 A點到 B 點共走兩次，試找出 2條這樣的路徑，使得取得的數(shù)之和為最大。無論是從 f[i1,j]還是 f[i,j1]走來，要么是 x坐標 +1，要么是 y坐標 +1，總歸 x坐標的