NOIP普及講座4-動(dòng)態(tài)規(guī)劃2課件

動(dòng)態(tài)規(guī)劃2NOIP普及講座4-動(dòng)態(tài)規(guī)劃2點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本經(jīng)典例題講解【例題1】裝箱問(wèn)題（noiopenjudge8785）問(wèn)題描述：有一個(gè)箱子容量為V（正整數(shù)，0<=v<=20000），同時(shí)有n個(gè)物品（0<n<=30），每個(gè)物品有一個(gè)體積（正整數(shù)）。要求n個(gè)物品中，任取若干個(gè)裝入箱內(nèi)，使箱子的剩余空間為最小。輸入第一行是一個(gè)整數(shù)V，表示箱子容量。第二行是一個(gè)整數(shù)n，表示物品數(shù)。接下來(lái)n行，每行一個(gè)正整數(shù)（不超過(guò)10000），分別表示這n個(gè)物品的各自體積。輸出一個(gè)整數(shù)，表示箱子剩余空間。NOIP普及講座4-動(dòng)態(tài)規(guī)劃2點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本經(jīng)典例題講解樣例輸入2468312797樣例輸出0。NOIP普及講座4-動(dòng)態(tài)規(guī)劃2點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本經(jīng)典例題講解【問(wèn)題分析】狀態(tài)：f[i,j]代表前i個(gè)物體裝在j重的包里的最優(yōu)解方程：f[i,j]=max(f[i-1,j],f[i-1,j-a[i]);

NOIP普及講座4-動(dòng)態(tài)規(guī)劃2點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本【程序?qū)崿F(xiàn)】

NOIP普及講座4-動(dòng)態(tài)規(guī)劃2點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本經(jīng)典例題講解【例題2】寶石手鐲（usaco）問(wèn)題描述：貝茜在珠寶店閑逛時(shí)，買到了一個(gè)中意的手鐲。很自然地，她想從她收集的N(1<=N<=3,402)塊寶石中選出最好的那些鑲在手鐲上。對(duì)于第i塊寶石，它的重量為W_i(1<=W_i<=400)，并且貝茜知道它在鑲上手鐲后能為自己增加的魅力值D_i(1<=D_i<=100)。由于貝茜只能忍受重量不超過(guò)M(1<=M<=12,880)的手鐲，她可能無(wú)法把所有喜歡的寶石都鑲上。于是貝茜找到了你，告訴了你她所有寶石的屬性以及她能忍受的重量，希望你能幫她計(jì)算一下，按照最合理的方案鑲嵌寶石的話，她的魅力值最多能增加多少。NOIP普及講座4-動(dòng)態(tài)規(guī)劃2點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本經(jīng)典例題講解【輸入格式】輸入的第一行有兩個(gè)整數(shù)N(1<=N<=3,402)和M(1<=M<=12,880)，接下來(lái)的N行每行兩個(gè)整數(shù)，分別表示寶石重量和魅力值。【輸出格式】輸出只包括一行，這一行只包含一個(gè)整數(shù)，表示魅力值最多能增加多少?！緲永斎搿?707110069112【樣例輸出】3NOIP普及講座4-動(dòng)態(tài)規(guī)劃2點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本經(jīng)典例題講解【問(wèn)題分析】狀態(tài)：f[i,j]代表前i個(gè)寶石戴在j重的手上獲得的最大魅力值方程：f[i,j]=max(f[i-1,j],f[i-1,j-a[i])+b[i];

NOIP普及講座4-動(dòng)態(tài)規(guī)劃2點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本【程序?qū)崿F(xiàn)】

NOIP普及講座4-動(dòng)態(tài)規(guī)劃2點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本經(jīng)典例題講解【例題3】奶牛打工問(wèn)題描述：奶牛Bassie去DQ打工，遇到一個(gè)客人給了一張好大面值的鈔票，于是Bassie不得不為了給這位顧客找零而面對(duì)這樣一個(gè)問(wèn)題：現(xiàn)在店里一共有n種硬幣，對(duì)這些不同種的硬幣進(jìn)行編號(hào)，編號(hào)為i的硬幣面值為a[i]。因?yàn)槟膛５氖种割^是有限的，因此他只能向你求助啦。(已知總需找零數(shù)為total)(1<=total<=1000,1<=n<=1000,1<=a[i]<=300)求一共有多少種解決方案？NOIP普及講座4-動(dòng)態(tài)規(guī)劃2點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本經(jīng)典例題講解【輸入格式】第一行為硬幣總值total和硬幣種類數(shù)n。以下n行為數(shù)值a[i]，i=1,2,3...n【輸出格式】一行，解決方案數(shù)【樣例輸入】83550251051【樣例輸出】159NOIP普及講座4-動(dòng)態(tài)規(guī)劃2點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本經(jīng)典例題講解0x500x250x100x583x10x500x250x101x578x10x500x250x102x573x10x500x250x103x568x10x500x250x104x563x10x500x250x105x558x10x500x250x106x553x10x500x250x107x548x10x500x250x108x543x10x500x250x109x538x10x500x250x1010x533x10x500x250x1011x528x10x500x250x1012x523x10x500x250x1013x518x10x500x250x1014x513x1

【樣例說(shuō)明】

NOIP普及講座4-動(dòng)態(tài)規(guī)劃2點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本經(jīng)典例題講解【問(wèn)題分析】狀態(tài)：f[i]代表面值為i的錢的換錢方案數(shù)方程：f[i]=sum(f[i-a[k]])1<=k<=n;

NOIP普及講座4-動(dòng)態(tài)規(guī)劃2點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本【程序?qū)崿F(xiàn)】

NOIP普及講座4-動(dòng)態(tài)規(guī)劃2點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本經(jīng)典例題講解【例題4】滑雪問(wèn)題描述：Michael喜歡滑雪。這并不奇怪，因?yàn)榛┑拇_很刺激。可是為了獲得速度，滑的區(qū)域必需向下傾斜，而且當(dāng)你滑到坡底，你不得不再次走上坡或者等待升降機(jī)來(lái)載你。Michael想知道在一個(gè)區(qū)域中最長(zhǎng)的滑坡。區(qū)域由一個(gè)二維數(shù)組給出。數(shù)組的每個(gè)數(shù)字代表點(diǎn)的高度。NOIP普及講座4-動(dòng)態(tài)規(guī)劃2點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本經(jīng)典例題講解下面是一個(gè)例子12345161718196152425207142322218131211109一個(gè)人可以從某個(gè)點(diǎn)不滑向上下左右相鄰四個(gè)點(diǎn)之一，當(dāng)且僅當(dāng)高度減小，在上面的例子中，一條可行的不滑坡為24－17－16－1（從24開(kāi)始，在1結(jié)束）。當(dāng)然25－24－23－…－3－2－1更長(zhǎng)。事實(shí)上，這是最長(zhǎng)的一條。【輸入格式】第1行為表示區(qū)域的二維數(shù)組的行數(shù)R和列數(shù)C(1≤R，C≥100)。下面是R行，每行有C個(gè)數(shù)，代表高度?！据敵龈袷健繀^(qū)域中最長(zhǎng)滑坡的長(zhǎng)度NOIP普及講座4-動(dòng)態(tài)規(guī)劃2點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本經(jīng)典例題講解【樣例輸入】551

2

345161718196152425207142322218131211109【樣例輸出】25

NOIP普及講座4-動(dòng)態(tài)規(guī)劃2點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本經(jīng)典例題講解【問(wèn)題分析】

一個(gè)類似最長(zhǎng)下降序列，窮舉每個(gè)最低點(diǎn)。用記憶化搜索寫(xiě)比較方便。NOIP普及講座4-動(dòng)態(tài)規(guī)劃2點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本【程序?qū)崿F(xiàn)】

NOIP普及講座4-動(dòng)態(tài)規(guī)劃2點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本經(jīng)典例題講解【例題5】最小代價(jià)子母樹(shù)問(wèn)題描述：有n堆沙子排成一排，每堆沙子有一個(gè)數(shù)量，例如：13

7

8

16

21

4

18。任意2堆相鄰的沙子可以進(jìn)行合并，將兩堆沙子合并為一堆時(shí)，兩堆沙子數(shù)量的和稱為合并這兩堆沙子的代價(jià)。經(jīng)過(guò)不斷的歸并，最后將這些沙子歸為一堆，而全部歸并代價(jià)的和稱為總代價(jià)。例如上列數(shù)，其中2種歸并方案的代價(jià)為：第1種的總代價(jià)為20+24+25+44+69+87=267

第2種的總代價(jià)為15+37+22+28+59+87=248

由此可見(jiàn)，不同的歸并過(guò)程得到的總代價(jià)是不一樣的。

問(wèn)題：當(dāng)n個(gè)數(shù)給出后，找出一種合理的歸并方法，使得總代價(jià)最小。NOIP普及講座4-動(dòng)態(tài)規(guī)劃2點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本點(diǎn)擊添加文本經(jīng)典例題講解【問(wèn)題分析】

狀態(tài)：f[i,j]代表從i堆合并到j(luò)堆所需要的最小代價(jià)方程

f[i,j]=min(f[i,k]+f[k+1,j])+s[j]-s[i-1];i<=k<=jNOIP普及講