noip動態(tài)規(guī)劃講解ppt課件-展示頁
2025-05-14 18:15本頁面
【正文】 【輸入文件】 第 1行，為兩個(gè)正整數(shù) N m（ 其中 N（ 32022） 表示總錢數(shù)， m（ 60） 為希望購買物品的個(gè)數(shù)。 設(shè)第 j件物品的價(jià)格為 v[j]， 重要度為 w[j]， 共選中了 k件物品，編號依次為 j1，j2， …… ， jk， 則所求的總和為： v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk] 。他還從因特網(wǎng)上查到了每件物品的價(jià)格（都是 10元的整數(shù)倍）。金明想買的東西很多，肯定會超過媽媽限定的 N元。每個(gè)主件可以有 0個(gè)、 1個(gè)或 2個(gè)附件。今天一早，金明就開始做預(yù)算了，他把想買的物品分為兩類：主件與附件，附件是從屬于某個(gè)主件的。 Sample Problem4 金明的預(yù)算方案（ NOIp2022） 【問題描述】 金明今天很開心，家里購置的新房就要領(lǐng)鑰匙了，新房里有一間金明自己專用的很寬敞的房間。 求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過背包容量，且價(jià)值總和最大。 完全背包： 有 N種物品和一個(gè)容量為 V的背包，每種物品都有無限件可用。第 i件物品的費(fèi)用是 c[i]， 價(jià)值是 w[i]。 輸入導(dǎo)彈依次飛來的高度 （ 雷達(dá)給出的高度數(shù)據(jù)是不大于 30000的正整數(shù) ） ，計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈 ， 如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng) 。 某天 ， 雷達(dá)捕捉到敵國的導(dǎo)彈來襲 。 Sample Problem2 攔截導(dǎo)彈 （ NOIp1999） 某國為了防御敵國的導(dǎo)彈襲擊 ， 發(fā)展出一種導(dǎo)彈攔截系統(tǒng) 。 第一行有 n個(gè)整數(shù) ， 用空格分隔 ， 第 i個(gè)整數(shù) Ti(130=Ti=230)是第 i位同學(xué)的身高 。 你的任務(wù)是 ， 已知所有 N位同學(xué)的身高 ， 計(jì)算最少需要幾位同學(xué)出列 ， 可以使得剩下的同學(xué)排成合唱隊(duì)形 。 合唱隊(duì)形 （ NOIp2022） 【 問題描述 】 N位同學(xué)站成一排 ， 音樂老師要請其中的 (NK)位同學(xué)出列 ， 使得剩下的 K位同學(xué)排成合唱隊(duì)形 。最長的不下降序列就是求長度最長的子序列 。 若存在 i1i2i3 … ie 且有 a(i1)a(i2) … a(ie)則稱為長度為 e的不下降序列。因此，掌握基本的 NOIp動態(tài)規(guī)劃題是至關(guān)重要的。 動態(tài)規(guī)劃是信息學(xué)競賽中選手必須熟練掌握的一種算法 ,它以其多元性廣受出題者的喜愛。歷屆 NOIp動態(tài)規(guī)劃講解 動態(tài)規(guī)劃 (dynamic programming)是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過程最優(yōu)化的數(shù)學(xué)方法。動態(tài)規(guī)劃算法把多階段過程轉(zhuǎn)化為一系列單階段問題，利用各階段之間的關(guān)系，逐個(gè)求解，以得到全局最優(yōu)策略。近年來，動態(tài)規(guī)劃幾乎每次都出現(xiàn)在 NOIp的賽場上，而且還有越來越多的趨勢。 動態(tài)規(guī)劃實(shí)質(zhì)： 枚舉 + 遞推 狀態(tài) 狀態(tài)轉(zhuǎn)移方程 Sample Problem1 1 3 5 9 1 從樹的根到樹的葉節(jié)點(diǎn)，最多能取多少數(shù)？ 貪心 ： 答案錯誤 暴力搜索 ： 如果數(shù)據(jù)大會超時(shí) 我們先將 NOIp里的動態(tài)規(guī)劃分分類： 最長不降子序列 背包 方格取數(shù) 石子歸并 狀態(tài)壓縮 數(shù)學(xué)遞推 順序遞推 設(shè)有由 n個(gè)不相同的整數(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。如上例中 3，18， 23， 24就是一個(gè)長度為 4的不下降序列，同時(shí)也有 3， 7， 10， 12， 16， 24長度為 6的不下降序列。 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。 合唱隊(duì)形是指這樣的一種隊(duì)形：設(shè) K位同學(xué)從左到右依次編號為 1， 2… ， K，他 們 的 身 高 分 別 為 T1， T2， … ， TK， 則 他 們 的 身 高 滿 足T1...TiTi+1… TK(1=i=K)。 【 輸入文件 】 輸入文件第一行是一個(gè)整數(shù) N(2=N=100)， 表示同學(xué)的總數(shù) 。 【 輸出文件 】 輸出文件包括一行 ， 這一行只包含一個(gè)整數(shù) ， 就是最少需要幾位同學(xué)出列 。 但是這種導(dǎo)彈攔截系統(tǒng)有一個(gè)缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度 ， 但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度 。 由于該系統(tǒng)還在試用階段 ， 所以只有一套系統(tǒng) ， 因此有可能不能攔截所有的導(dǎo)彈 。 樣例： 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件物品和一個(gè)容量為 V的背包。 求解將哪些物品裝入背包可使價(jià)值總和最大。第 i種物品的費(fèi)用是 c[i]， 價(jià)值是w[i]。 For i:=1 To n Do For j:=Max Downto a[i] Do (a[i] To Max) If f[j]f[ja[i]]+b[i] Then f[j]:=f[ja[i]]+b[i]。更讓他高興的是，媽媽昨天對他說：“你的房間需要購買哪些物品，怎么布置，你說了算，只要不超過 N元錢就行”。如果要買歸類為附件的物品，必須先買該附件所屬的主件。附件不再有從屬于自己的附件。于是，他把每件物品規(guī)定了一個(gè)重要度，分為5等：用整數(shù) 1~5表示，第 5等最重要。他希望在不超過 N元（可以等于 N元）的前提下，使每件物品的價(jià)格與重要度的乘積的總和最大。（ 其中 *為乘號） 請你幫助金明設(shè)計(jì)一個(gè)滿足要求的購物單。）從第 2行到第 m+1行，第 j行給出了編號為 j1的物品的基本數(shù)據(jù)，每行有 3個(gè)非負(fù)整數(shù) v p q（ 其中 v表示該物品的價(jià)格（ v10000）， p表示該物品的重要度（ 1~5）， q表示該物品是主件還是附件?！据斎霕永? 1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0 【輸出樣例】 2200 For i:=1 To n Do
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1