動(dòng)態(tài)規(guī)劃專題講義

1、動(dòng)態(tài)規(guī)劃專題講義第1頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一前言本文只是個(gè)人對動(dòng)態(tài)規(guī)劃的一些見解,理論性并不一定能保證正確,有不足和缺漏之處請諒解和及時(shí)地指出.第2頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一動(dòng)態(tài)規(guī)劃 是信息學(xué)競賽中選手必須熟練掌握的一種算法,他以其多元性廣受出題者的喜愛.動(dòng)態(tài)規(guī)劃第3頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一目錄什么是動(dòng)態(tài)規(guī)劃狀態(tài) 階段 決策一種確立狀態(tài)的方法兩種簡單的動(dòng)規(guī)武器三種特殊的動(dòng)態(tài)規(guī)劃第4頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一什么是動(dòng)態(tài)規(guī)劃在學(xué)習(xí)動(dòng)態(tài)規(guī)劃之前你一定學(xué)過搜索.那么搜索與

2、動(dòng)態(tài)規(guī)劃有什么關(guān)系呢?我們來下面的一個(gè)例子.back第5頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一數(shù)字三角形給你一個(gè)數(shù)字三角形, 形式如下: 1 2 3 4 5 67 8 9 10找出從第一層到最后一層的一條路,使得所經(jīng)過的權(quán)值之和最小或者最大.back第6頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一數(shù)字三角形無論對與新手還是老手，這都是再熟悉不過的題了，很容易地，我們寫出狀態(tài)轉(zhuǎn)移方程：f(i, j)=ai, j + minf(i-1, j)+f(i-1, j + 1)對于動(dòng)態(tài)規(guī)劃算法解決這個(gè)問題，我們根據(jù)狀態(tài)轉(zhuǎn)移方程和狀態(tài)轉(zhuǎn)移方向，比較容易地寫出動(dòng)態(tài)規(guī)劃的循環(huán)表

3、示方法。但是，當(dāng)狀態(tài)和轉(zhuǎn)移非常復(fù)雜的時(shí)候，也許寫出循環(huán)式的動(dòng)態(tài)規(guī)劃就不是那么簡單了。 解決方法：back記憶化搜索 第7頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一記憶化搜索我們嘗試從正面的思路去分析問題，如上例，不難得出一個(gè)非常簡單的遞歸過程 :f1:=f(i-1,j+1); f2:=f(i-1,j);if f1f2 then f:=f1+ai,j else f:=f2+ai,j;顯而易見，這個(gè)算法就是最簡單的搜索算法。時(shí)間復(fù)雜度為2n，明顯是會(huì)超時(shí)的。分析一下搜索的過程，實(shí)際上，很多調(diào)用都是不必要的，也就是把產(chǎn)生過的最優(yōu)狀態(tài)，又產(chǎn)生了一次。為了避免浪費(fèi)，很顯然，我們存放一個(gè)o

4、pt數(shù)組： back第8頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一記憶化搜索Opti, j - 每產(chǎn)生一個(gè)f(i, j)，將f(i, j)的值放入opt中，以后再次調(diào)用到f(i, j)的時(shí)候，直接從opti, j來取就可以了。于是動(dòng)態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程被直觀地表示出來了，這樣節(jié)省了思維的難度，減少了編程的技巧，而運(yùn)行時(shí)間只是相差常數(shù)的復(fù)雜度，而且在相當(dāng)多的情況下，遞歸算法能更好地避免浪費(fèi)，在比賽中是非常實(shí)用的.記憶化的功效back第9頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一動(dòng)態(tài)規(guī)劃的實(shí)質(zhì)可以看出動(dòng)態(tài)規(guī)劃的實(shí)質(zhì)就是這也就是為什么我們常說動(dòng)態(tài)規(guī)劃必須滿足重疊子問題

5、的原因.記憶化,正符合了這個(gè)要求.記憶化搜索第10頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一狀態(tài) 階段 決策或許有一種對動(dòng)態(tài)規(guī)劃的簡單稱法,叫分階段決策.其實(shí)我認(rèn)為這個(gè)稱法并不是很能讓人理解.那么下面我們來看看階段,狀態(tài),決策這三者間得關(guān)系吧.back第11頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一狀態(tài) 階段 決策狀態(tài)是表現(xiàn)出動(dòng)態(tài)規(guī)劃核心思想的一個(gè)東西.而分階段決策這個(gè)東西有似乎沒有提到狀態(tài),這是不科學(xué)的.階段,有些題目并不一定表現(xiàn)出一定的階段性.數(shù)字三角形的階段就是每一層.這里我們引入一個(gè)概念-以前狀態(tài).但階段不是以前狀態(tài),狀態(tài)是階段的表現(xiàn)形式.數(shù)字三角形的以

6、前狀態(tài)就是當(dāng)前層的前一層.那什么是決策呢?我們看看下面一張圖就知道了.back第12頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一決策當(dāng)前狀態(tài)以前狀態(tài)決策顯然,從上圖可以看出,當(dāng)前狀態(tài)通過決策,回到了以前狀態(tài).可見決策其實(shí)就是狀態(tài)之間的橋梁。而以前狀態(tài)也就決定了當(dāng)前狀態(tài)的情況。數(shù)字三角形的決策就是選擇相鄰的兩個(gè)以前狀態(tài)的最優(yōu)值。back第13頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一動(dòng)規(guī)的要訣狀態(tài)我們一般在動(dòng)規(guī)的時(shí)候所用到的一些數(shù)組，也就是用來存儲(chǔ)每個(gè)狀態(tài)的最優(yōu)值的。我們就從動(dòng)態(tài)規(guī)劃的要訣，也就是核心部分“狀態(tài)”開始，來逐步了解動(dòng)態(tài)規(guī)劃。back第14頁，共74頁，

7、2022年，5月20日，15點(diǎn)16分，星期一攔截導(dǎo)彈攔截導(dǎo)彈（Noip2002） 某國為了防御敵國的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng) 有一個(gè)缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高 于前一發(fā)的高度。 某天，雷達(dá)捕捉到敵國的導(dǎo)彈來襲。由于該系統(tǒng)還在試用階段，所以 只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。輸入導(dǎo)彈依次飛來的高度，計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈。第15頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一攔截導(dǎo)彈狀態(tài)的表示fi，表示當(dāng)?shù)趇個(gè)導(dǎo)彈必須選擇時(shí)，前i個(gè)導(dǎo)彈最多能攔截多少。每個(gè)導(dǎo)彈有一定的高度，當(dāng)前狀態(tài)就是以第i個(gè)導(dǎo)

8、彈為最后一個(gè)打的導(dǎo)彈。以前狀態(tài)就是在這個(gè)導(dǎo)彈以前打的那個(gè)導(dǎo)彈。顯然這是十分能夠體現(xiàn)狀態(tài)間的聯(lián)系的題目。back第16頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一最長公共子串給出兩個(gè)字符串序列。求出這樣的一個(gè)最長的公共子串：子串中的每個(gè)字符都能在兩個(gè)原串中找到，而且每個(gè)字符的順序和原串中的順序一致。第17頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一交錯(cuò)匹配交錯(cuò)匹配（最長公共子串的改編） 給你兩排數(shù)字,只能將兩排中數(shù)字相同的兩個(gè)位置相連,而每次相連必須有兩個(gè)匹配形成一次交錯(cuò),交錯(cuò)的連線不能再和別的交錯(cuò)連線有交點(diǎn).問這兩排數(shù)字最多能形成多少個(gè)交錯(cuò)匹配.2 3 3 2 4

9、1 5 1 3 5 103 1 2 3 2 4 12 1 5 5 3 狀態(tài)的表示fi,j表示前i個(gè)第一排的數(shù)字和前j個(gè)第二排的數(shù)字搭配的最優(yōu)值。當(dāng)前的狀態(tài)就是當(dāng)前你枚舉到的一組交錯(cuò)的后面兩個(gè)位置.例如上圖中當(dāng)前狀態(tài)是3和1(第一組交錯(cuò)),枚舉他的以前狀態(tài)就有1 3.這樣在1 3之前會(huì)有一個(gè)最優(yōu)值存在,因此可以由此得到3 1的最優(yōu)值.back第18頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一買車票買車票(Ural1031) Ekaterinburg城到Sverdlovsk城有直線形的鐵路線。兩城之間還有其他一些?？空?總站數(shù)為N。各站按照離Ekaterinburg城的距離編號。Ek

10、aterinburg城編號為1，Sverdlovsk城編號為N。back第19頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一買車票某兩站之間車票價(jià)格由這兩站的距離X決定. 當(dāng)0X=L1時(shí)，票價(jià)為C1元. 當(dāng)L1X=L2時(shí)，票價(jià)為C2元. 當(dāng)L2X=L3時(shí)，票價(jià)為C3元.當(dāng)兩站距離大于L3時(shí)沒有直達(dá)票，所以有時(shí)候要買幾次票做幾次車才行。比如，在上面的例圖中，2-6沒有直達(dá)票，有幾種買票方法可以從2-6，其中一種是買C2元的2-3車票，再買C3元的3-6車票。back第20頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一買車票給定起點(diǎn)站和終點(diǎn)站還有L1,L2,L3,C1,C2

11、,C3，求出要從起點(diǎn)到終點(diǎn)最少要花多少錢.怎么辦確定題目的當(dāng)前狀態(tài)與以前狀態(tài)!back第21頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一買車票當(dāng)前狀態(tài)以前狀態(tài)當(dāng)前所在的某個(gè)車站這一題的以前狀態(tài)其實(shí)只有3種.即滿足3種距離(收費(fèi))情況的3個(gè)車站.要知道這3個(gè)車站可以先做一個(gè)預(yù)處理.顯然這3個(gè)車站在滿足距離限制的條件下應(yīng)該越遠(yuǎn)越好.back第22頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一買車票預(yù)處理 很容易想出一個(gè)N2的預(yù)處理,但是那樣是會(huì)超時(shí)的.由于盡量要讓車站離得遠(yuǎn)(費(fèi)用是一樣的啊 )因此在每種收費(fèi)情況下,每個(gè)車站的以前狀態(tài)車站一定是遞增的序列.這里是只要O(N)

12、的程序: for j:=1 to 3 do begin k:=en-1; for i:=en downto be do begin while (wayi-wayk=be) do dec(k); pij:=k+1; end; end; 數(shù)組Pij表示的是I狀態(tài)的第j種以前狀態(tài).back第23頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一買車票動(dòng)態(tài)規(guī)劃的部分for i:=be+1 to en do 枚舉當(dāng)前狀態(tài) begin costi:=maxlongint; for j:=1 to 3 do 枚舉以前狀態(tài) beginif (piji) and (costi costpij + cj

13、) then costi:=costpij+cj; end; end;back第24頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一動(dòng)規(guī)的要訣狀態(tài)有時(shí)候當(dāng)前狀態(tài)確定后,以前狀態(tài)就已經(jīng)確定,則無需枚舉.back第25頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一Tom的煩惱Tom是一個(gè)非常有創(chuàng)業(yè)精神的人，由于大學(xué)學(xué)的是汽車制造專業(yè)，所以畢業(yè)后他用有限的資金開了一家汽車零件加工廠， 專門為汽車制造商制造零件。由于資金有限，他只能先購買一臺(tái)加工機(jī)器?，F(xiàn)在他卻遇到了麻煩，多家汽車制造商需要他加 工一些不同零件（由于廠家和零件不同，所以給的加工費(fèi)也不同），而且不同廠家對于不同零件的

14、加工時(shí)間要求不同（有些加工時(shí)間要求甚至是沖突的，但開始和結(jié)束時(shí)間相同不算沖突）。Tom當(dāng)然希望能把所有的零件都加工完，以得到更多的加工費(fèi)，但當(dāng)一些零件的加工時(shí)間要求有沖突時(shí)，在某個(gè)時(shí)間內(nèi)他只能選擇某種零件加工（因?yàn)樗挥幸慌_(tái)機(jī)器），為了賺得盡量多的加工費(fèi)，Tom不知如何進(jìn)行取舍。 第26頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一Tom的煩惱Tom的煩惱 按結(jié)束時(shí)間排序，枚舉結(jié)束時(shí)間作為當(dāng)前狀態(tài),以前狀態(tài)就是該結(jié)束時(shí)間對應(yīng)的起始時(shí)間，這是已經(jīng)確定的.back第27頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一文字游戲文字游戲(fairfox邀請賽1) 給你一份單詞表，

15、和一個(gè)句子。求出該句子能有多少中不同的劃分方法.例如: 單詞是ab cd a b c d 句子是abcd 他共有4種完全劃分方案: ab/cd a/b/c/d a/b/cd ab/c/d; 當(dāng)前狀態(tài)就是單詞在句子中向后靠的位置,以前狀態(tài)就是確定這個(gè)單詞位置以后,除掉這個(gè)單詞長度后的一個(gè)位置.狀態(tài)轉(zhuǎn)移方程是:Fi:=Fi+Fi-length(wordj) IOI中有一題前綴也是類似的題目.第28頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一決策中的定量狀態(tài)轉(zhuǎn)移方程的構(gòu)造無疑是動(dòng)態(tài)規(guī)劃過程中最重要的一步,也是最難的一步.對于大多數(shù)的動(dòng)態(tài)規(guī)劃,尋找狀態(tài)轉(zhuǎn)移方程有一條十分高效的通道,就是尋

16、找變化中的不變量.定量處理的過程也就是決策實(shí)施的過程.尋找定量back第29頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一尋找定量最佳加法表達(dá)式有一個(gè)由1.9組成的數(shù)字串.問如果將m個(gè)加號插入到這個(gè)數(shù)字串中.使得所形成的算術(shù)表達(dá)式的值最小.Problem或許你不明白我在說什么,那么我們通過題目來說明吧back第30頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一最佳加法表達(dá)式這一題中的定量是什么呢?因?yàn)槭翘砣爰犹?那么添完加號后,表達(dá)式的最后一定是個(gè)數(shù)字串,這就是定量.從這里入手,不難發(fā)現(xiàn)可以把以前狀態(tài)認(rèn)為是在前i個(gè)字符中插入k-1個(gè)加號(這里的i是當(dāng)作決策在枚舉),然后

17、i+1到最后一位一定是整個(gè)沒有被分割的數(shù)字串,第k個(gè)加號就添在i與i+1個(gè)數(shù)字之間.這樣就構(gòu)造出了整個(gè)數(shù)字串的最優(yōu)解.而至于前i個(gè)字符中插入k-1個(gè)加號,這又回到了原問題的形式,也就是回到了以前狀態(tài),所以狀態(tài)轉(zhuǎn)移方程就能很快的構(gòu)造出來了.back第31頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一最佳加法表達(dá)式用fi,j,表示的是在前i個(gè)字符中插入j個(gè)加號能達(dá)到的最小值,最后的答案也就是Flength(s),m.于是就有一個(gè)動(dòng)規(guī)的方程: Fi,j:=min(fi,j,fk,j-1+numk+1,i) numk+1,i表示k+1位到i位所形成的數(shù)字.這里顯然是把加號插入了第k+1個(gè)位

18、置上.知道了這一題怎么做以后,乘積最大的一題也是完全一樣的形式,誰還會(huì)去用搜索?back第32頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一定量現(xiàn)在大概大家已經(jīng)了解了定量是什么,那么我們下面通過幾道題目來了解一下定量的威力.back第33頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一游戲游戲(Noip2003普及組)這一題的描述簡單說一下:在一個(gè)圈的周圍有n個(gè)石子,將他們劃分成m堆(每堆中的石子必須連續(xù)相鄰),每一堆石子計(jì)算出他們的總重量mod10的值,然后將這些值相乘,求得到的結(jié)果最大最小值是多少.back第34頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期

19、一游戲這一題作者其實(shí)是根據(jù)最佳加法表達(dá)式改編的.但是他加了一個(gè)在圈上的條件,怎么辦呢?尋找定量!back第35頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一游戲可想而知,因?yàn)橹辽僖殖?堆,那么至少有兩個(gè)石子之間是會(huì)被分隔開的.這就是定量!當(dāng)劃分?jǐn)?shù)1時(shí),一定有兩個(gè)相鄰石子被劃分到不同的堆里去!于是這個(gè)圈被這樣的理解斷成了一條線,解法就和最佳加法表達(dá)式一樣了.當(dāng)然這個(gè)斷開的位置是需要枚舉的,然后保留下一個(gè)最優(yōu)值.顯然這個(gè)斷開的操作對整個(gè)過程沒有影響,因?yàn)檫@是必然的情況,這是定量!back第36頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一最優(yōu)三角形劃分問題描述給定一具有N

20、（N50）個(gè)頂點(diǎn)(從1到N編號）的凸多邊形，每個(gè)頂點(diǎn)的權(quán)均已知。問如何把這個(gè)凸多邊形劃分成N-2個(gè)互不相交的三角形，使得這些三角形頂點(diǎn)的權(quán)的乘積之和最小？ back第37頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一最優(yōu)三角形劃分這一題大概搜都是十分麻煩的,可是這一題Dp的話,比搜索要容易實(shí)現(xiàn)和容易理解得多.先得表示一下狀態(tài),我們用fi,j表示以第i個(gè)點(diǎn)開頭,順時(shí)針長度為j的一塊子多邊形.如上圖中f1,5表示的子多邊形(黑色虛線劃開)back第38頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一最優(yōu)三角形劃分如果沒有紅色虛線的部分,或許你會(huì)認(rèn)為決策應(yīng)該是枚舉子多邊形內(nèi)的兩

21、點(diǎn)連線,然后分成兩個(gè)子多邊形.這顯然是不行的,因?yàn)橛?jì)算機(jī)已經(jīng)無法再表示分割出來的子多邊形了(不能用fi,j來表示了).back第39頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一最優(yōu)三角形劃分那么我們該如何決策呢?尋找定量!顯然可以發(fā)現(xiàn),fi,j表示的子多邊形有一條邊是在內(nèi)部的(黑色虛線),而這一條邊在該子多邊形內(nèi)必定屬于某個(gè)三角形,因?yàn)槲覀冞x擇了該子多邊形作為一種狀態(tài),那么就一定存在那條虛線黑邊,所以一定存在所說的三角形.于是我們枚舉這個(gè)三角形的另外一個(gè)點(diǎn)在子多邊形的位置,則可以把子問題還原到原問題(因?yàn)樵撊切伟讯噙呅蝿澇闪藘蓚€(gè)可以用表示的多邊形和一個(gè)三角形).這些再次分割出的

22、子多邊形就是以前狀態(tài),而剛才的多邊形則是當(dāng)前狀態(tài).back第40頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一定量其實(shí)定量的作用就是為了寫出狀態(tài)轉(zhuǎn)移方程,即讓人能迅速找出狀態(tài)之間的關(guān)系(決策).通過定量的處理,當(dāng)前狀態(tài)又回到了以前狀態(tài),選手就可以知道,這一題就是要用動(dòng)態(tài)規(guī)劃來求解了.back第41頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一定量我們來看看剛才的一些題目的定量.交錯(cuò)匹配:一定存在最后一組交錯(cuò)(這好像是廢話),所以枚舉這個(gè)最后的交錯(cuò)的位置作為狀態(tài),這樣就回到以前狀態(tài).買車票:定量1:一定有最后一個(gè)車站(這個(gè)作為狀態(tài));定量2:某個(gè)車站一定是由某個(gè)前面的車站

23、到達(dá)的.(導(dǎo)彈攔截也是這樣)數(shù)字三角形:某個(gè)點(diǎn)一定是由他上面的相鄰兩點(diǎn)到達(dá)的.(過河卒也是這樣)定量很不錯(cuò)啊!第42頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一動(dòng)態(tài)規(guī)劃的武器在動(dòng)規(guī)的操作過程中,或者是操作過程前,有一些很常用的武器,這里簡要介紹兩種:排序填鴨back第43頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一排序武器一:排序遇到過很多需要排序的動(dòng)態(tài)規(guī)劃題目,如果不排序,動(dòng)規(guī)的思想很難體現(xiàn).back第44頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一Tom的煩惱Tom的煩惱 這是大家熟知的一題,如果不排序的話,復(fù)雜度便是N2,按起始時(shí)間排序復(fù)雜度也是

24、N2,二按結(jié)束時(shí)間排序之后復(fù)雜度降為了NlogN.back第45頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一巴比倫塔巴比倫塔問題描述: 有很多的不同種類的立方體(長寬高不同),每一類有無限多個(gè).將他們一層層的疊加起來,要求上面的一塊立方體的下底面一定要比下面的一塊立方體的上底面要小,就是長和寬都要小于.問最多能建成多高的塔.back第46頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一巴比倫塔經(jīng)過研究可以發(fā)現(xiàn),每一種類的立方體有3種不同的擺放方式,而每種擺放方式最多用1次,所以可以分離出3*N塊“不同”的立方體,接下來,或許你仍然不知道如何動(dòng)規(guī),那么就試試排序.列出所有

25、的石塊的所有擺放方式xi,yi,zi.必須全部保證xiyi.然后按關(guān)鍵字xi,yi,zi的大小順序排序.這樣就可以進(jìn)行十分簡單的類似與導(dǎo)彈攔截的一個(gè)動(dòng)態(tài)規(guī)劃的處理了.限制條件是xi和yi,代價(jià)值是zi(高度).back第47頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一滑雪滑雪(上海2002)題目的大意是給出一個(gè)矩陣,如:對于所給出的矩陣找出一條最長的遞減鏈,滿足鏈中相鄰的兩個(gè)元素間都是在矩陣中相鄰的.上圖中所給出的矩陣中的最長鏈?zhǔn)? 2 3 425.back第48頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一滑雪對于有給出的數(shù)字進(jìn)行遞減排序,然后兩重循環(huán)就搞定問題.動(dòng)

26、態(tài)轉(zhuǎn)移方程是: Fi:=max(Fi,Fj+1); 滿足條件是i與j在原矩陣中相鄰.試想,如果你不知道要排序,你能想到這題是用動(dòng)態(tài)規(guī)劃嗎?back第49頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一填鴨武器二:填鴨這個(gè)思想帶有枚舉的感覺.就是開個(gè)大數(shù)組,把代價(jià)值一個(gè)個(gè)填進(jìn)去.back第50頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一硬幣問題硬幣問題（經(jīng)典問題） 就是給出n種硬幣的面值,問面值 M有多少種不同的表示方法. 動(dòng)態(tài)轉(zhuǎn)移方程是Fi:=Fi+FI-costj.當(dāng)前狀態(tài)是i,以前狀態(tài)是i-costj.多米諾骨牌（某題的簡化） 有N張多米諾骨牌,每張的兩端有兩個(gè)數(shù)字

27、,范圍在1.6之間.每張骨牌可以正放,也可以反放.求出一種擺放的情況,使得所有的骨牌上端數(shù)字之和與下端數(shù)字之和的差值最小.求出最小差值.back第51頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一多米諾骨牌可以這么考慮這個(gè)問題:我們把每一個(gè)骨牌的上下差值記下。接下來的任務(wù)便是將這些值分成兩組，使得他們的和的差值最小。動(dòng)規(guī)過程如下：f0:=true; for i:=1 to n do for j:=sum downto ai do fj:=fj or fj-ai;Sum表示所有差值的和. ai表示第i塊骨牌的差值. J是當(dāng)前狀態(tài),j-ai是以前狀態(tài).fj表示j這個(gè)差值能否通過組合得到

28、。接下來的程序就不用我多說了。back第52頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一商店購物商店購物(IOI) 這一題更是需要開一個(gè)五維bool型數(shù)組.還需要通過遞歸求出組合形式.動(dòng)規(guī)的方程我就不寫了.back第53頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一動(dòng)態(tài)規(guī)劃的武器講完了比較實(shí)用的兩種種動(dòng)規(guī)的武器之后,我們來看看一些大家可能不太會(huì)做的動(dòng)規(guī)類型第54頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一特殊的動(dòng)規(guī)這里我講講三種特殊的動(dòng)態(tài)規(guī)劃:圖狀動(dòng)規(guī),樹狀動(dòng)規(guī),二次動(dòng)規(guī).back第55頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一圖狀動(dòng)規(guī)城

29、堡某國聰明美麗的公主要找一位如意郎君，她希望未來的夫君是一個(gè)聰明善良，節(jié)儉但又不吝嗇的人。為了找到理想的人選，她的爸爸國王，給她修建了一座城堡，這個(gè)城堡有很多房間，房間之間有走廊連接，但每進(jìn)入一個(gè)房間必須要花費(fèi)一定數(shù)量的錢幣，公主就在某個(gè)房間中等待。開始，國王給每個(gè)候選人一樣多的錢幣，候選人從同一個(gè)地點(diǎn)出發(fā)，直到找到美麗的公主為止，如果這時(shí)哪個(gè)人找到了公主，并且錢幣剛好用完，那么他將會(huì)贏得公主的芳心。back第56頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一城堡乍看此題,似乎就是搜沒得說了,是嗎?如果告訴你這一題是動(dòng)態(tài)規(guī)劃的話,你會(huì)怎么做?狀態(tài)是什么動(dòng)態(tài)轉(zhuǎn)移方程是什么?back第

30、57頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一城堡既然是問我們能不能到達(dá),所以想想就應(yīng)該知道,動(dòng)規(guī)的數(shù)組是bool型的.一開始時(shí),只有出發(fā)的房間記為true.但是,并不是以每個(gè)房間作為狀態(tài),因?yàn)檫€存在一個(gè)把錢用光的問題.到達(dá)同一個(gè)房間時(shí),如果剩余的錢不一樣,也就會(huì)有不同的決策.所以狀態(tài)就是在剩余j個(gè)錢幣的時(shí)候能否到達(dá)第i個(gè)房間.用fi,j來表示.back第58頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一圖狀動(dòng)規(guī)于是動(dòng)態(tài)轉(zhuǎn)移方程也就出來了fi,j:=fi,j or fk,j+ciK表示的是和I連接的一個(gè)房間,ci表示進(jìn)入I號房間的花費(fèi).back第59頁，共74頁，2

31、022年，5月20日，15點(diǎn)16分，星期一樹狀動(dòng)規(guī)沒有上司的晚會(huì)某公司要舉辦一次晚會(huì)，但是為了使得晚會(huì)的氣氛更加活躍，每個(gè)參加晚會(huì)的人都不希望在晚會(huì)中見到他的上司，要不然他們會(huì)很掃興。現(xiàn)在已知每個(gè)人的活躍指數(shù)和上司關(guān)系（當(dāng)然不可能存在環(huán)），求邀請哪些人來能使得晚會(huì)的總活躍指數(shù)最大。 back第60頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一沒有上司的晚會(huì)按照要求構(gòu)建一張關(guān)系圖，可見這是一棵樹。對于這類最值問題，向來是用動(dòng)態(tài)規(guī)劃求解的。任何一個(gè)點(diǎn)的取舍可以看作一種決策，那么狀態(tài)就是在某個(gè)點(diǎn)取的時(shí)候或者不取的時(shí)候，以他為跟的子樹能有的最大活躍總值。分別可以用fi,1和fi,0表示。b

32、ack第61頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一沒有上司的晚會(huì)當(dāng)這個(gè)點(diǎn)取的時(shí)候，他的所有兒子都不能取，所以fi,1:=sum(fj,0,j為i的兒子)i的權(quán)值。不取的時(shí)候，他的所有兒子取不取無所謂，不過當(dāng)然應(yīng)該取價(jià)值最大的一種情況。所以fi,0:=sum(max(fj,1,fj,0),j為i的i兒子）。這就是樹狀動(dòng)規(guī)的基本形態(tài)。back第62頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一二次動(dòng)規(guī)在動(dòng)規(guī)的基礎(chǔ)上再進(jìn)行動(dòng)規(guī)，就叫做二次動(dòng)規(guī)。買票有一座n層的樓房，某個(gè)人要到第n層的任何一個(gè)房間買票。每層樓都有m個(gè)房間。而如果要到第i層的第j個(gè)房間買票，那么必須先在第

33、i-1層的第j個(gè)房間買票或者在第i層的與這個(gè)房間相鄰的房間買過票才行.而每個(gè)房間所要收取的票費(fèi)是不同的,給定每個(gè)房間內(nèi)買票需要的費(fèi)用,問要在第n層的任意一間房間內(nèi)買到票的最小消費(fèi)是多少.back第63頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一買票顯然不能寫這樣的狀態(tài)轉(zhuǎn)移方程:fi,j:=min(fi-1,j,fi,j-1,fi,j+1)+wj.因?yàn)闊o法有一種處理順序使得在fi,j之前同時(shí)求得fi,j-1和fi,j+1的最優(yōu)值.所以動(dòng)規(guī)分兩次進(jìn)行.第一次用狀態(tài)轉(zhuǎn)移方程fi,j:=min(fi,j-1,fi-1,j)+wi求出一個(gè)不一定是最優(yōu)的解.再用fi,j:=min(fi,j,

34、fi,j+1,j from m-1 downto 1)+wi求出最終的最優(yōu)解,可以證明這樣的能夠求出真正的最優(yōu)解.要注意的是這兩次動(dòng)規(guī)不能分開做,而要在處理每一層的時(shí)候都要做,要不然顯然無法求得最優(yōu)值。back第64頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一綜合題網(wǎng)絡(luò)（Ural1056,求樹的中心）題目大意是：有一棵有N個(gè)結(jié)點(diǎn)的樹，給出每個(gè)結(jié)點(diǎn)的父親（即給出這棵樹），邊的權(quán)都是1。每個(gè)結(jié)點(diǎn)延樹的邊可以走到樹的任意一個(gè)結(jié)點(diǎn)，令A(yù)i為第i個(gè)結(jié)點(diǎn)最遠(yuǎn)能走的距離，求出Ai最小的結(jié)點(diǎn)有哪些。如有多個(gè)最小的Ai，則都要輸出。這里N=10000 back第65頁，共74頁，2022年，5月2

35、0日，15點(diǎn)16分，星期一網(wǎng)絡(luò)枚舉每個(gè)點(diǎn)，然后DFS復(fù)雜度O(N2)，超時(shí)是顯然的事情?？梢园l(fā)現(xiàn)其實(shí)有很多DFS都重復(fù)做了同樣的工作，產(chǎn)生了浪費(fèi)，所以應(yīng)該選擇動(dòng)態(tài)規(guī)劃解決這個(gè)問題。樹上的動(dòng)規(guī)，是否直接可以寫出下面的狀態(tài)轉(zhuǎn)移方城呢？fi:=max(fson,ffather)+1 廢話，顯然是不行的，son和father的值不可能同時(shí)得到。但是不要放棄，解決這個(gè)沖突的方法，就是采用二次動(dòng)規(guī)。back第66頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一網(wǎng)絡(luò)第一次動(dòng)規(guī)做fi:=max(fson)+1，第二次動(dòng)規(guī)做fi:=max(fi,ffather + 1) 。但是存在一個(gè)問題就是如果ff

36、ather的值是從i那里得到的，這樣計(jì)算顯然就錯(cuò)了。不要放棄，在實(shí)際操作過程中，f需要記下兩個(gè)值，一個(gè)是最優(yōu)值，一個(gè)是次優(yōu)值，這兩個(gè)值必須由不用的子結(jié)點(diǎn)得到。這樣當(dāng)最優(yōu)值發(fā)生矛盾的時(shí)候，次優(yōu)值一定不會(huì)矛盾。問題就解決了。復(fù)雜度O(N)十分的理想。 back第67頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一總結(jié)動(dòng)態(tài)規(guī)劃有很多東西還需要我們更加努力地去探索和學(xué)習(xí).總體上說來,動(dòng)態(tài)規(guī)劃是個(gè)既簡單又不簡單的算法,熟練地掌握了動(dòng)態(tài)規(guī)劃,也就熟練地控制了比賽.back第68頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一Thats all!Thank you for listeni

37、ng.back第69頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一動(dòng)規(guī)練習(xí)題垃圾陷阱（USACO&TJU1087）卡門農(nóng)夫約翰極其珍視的一條Holsteins奶牛已經(jīng)落了到“垃圾井”中?！袄笔寝r(nóng)夫們?nèi)永牡胤?，它的深度為D (2 = D = 100)英尺。卡門想把垃圾堆起來，等到堆得與井同樣高時(shí)，她就能逃出井外了。另外，卡門可以通過吃一些垃圾來維持自己的生命。每個(gè)垃圾都可以用來吃或堆放，并且堆放垃圾不用花費(fèi)卡門的時(shí)間。假設(shè)卡門預(yù)先知道了每個(gè)垃圾扔下的時(shí)間t(0 t = 1000)，以及每個(gè)垃圾堆放的高度h(1 = h = 25)和吃進(jìn)該垃圾能維持生命的時(shí)間f(1 = f = 30)，要求出卡門最早能逃出井外的時(shí)間，假設(shè)卡門當(dāng)前體內(nèi)有足夠持續(xù)10小時(shí)的能量，如果卡門10小時(shí)內(nèi)沒有進(jìn)食，卡門就將餓死。 第70頁，共74頁，2022年，5月20日，15點(diǎn)16分，星期一動(dòng)規(guī)練習(xí)題字符串距離（TJU1086）設(shè)有字符串X，我們稱在X的頭尾及中間插入任意多個(gè)空格后構(gòu)成的新字符串為X的擴(kuò)展串，如字符串X為“abcbcd”，則字符串“abcbcd”，“abcbcd”和“abcbcd”都是X的擴(kuò)展串，這里“”