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

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

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

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

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

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

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

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

8、彈為最后一個打的導彈。以前狀態(tài)就是在這個導彈以前打的那個導彈。顯然這是十分能夠體現(xiàn)狀態(tài)間的聯(lián)系的題目。back第16頁，共74頁，2022年，5月20日，15點16分，星期一最長公共子串給出兩個字符串序列。求出這樣的一個最長的公共子串：子串中的每個字符都能在兩個原串中找到，而且每個字符的順序和原串中的順序一致。第17頁，共74頁，2022年，5月20日，15點16分，星期一交錯匹配交錯匹配（最長公共子串的改編） 給你兩排數(shù)字,只能將兩排中數(shù)字相同的兩個位置相連,而每次相連必須有兩個匹配形成一次交錯,交錯的連線不能再和別的交錯連線有交點.問這兩排數(shù)字最多能形成多少個交錯匹配.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個第一排的數(shù)字和前j個第二排的數(shù)字搭配的最優(yōu)值。當前的狀態(tài)就是當前你枚舉到的一組交錯的后面兩個位置.例如上圖中當前狀態(tài)是3和1(第一組交錯),枚舉他的以前狀態(tài)就有1 3.這樣在1 3之前會有一個最優(yōu)值存在,因此可以由此得到3 1的最優(yōu)值.back第18頁，共74頁，2022年，5月20日，15點16分，星期一買車票買車票(Ural1031) Ekaterinburg城到Sverdlovsk城有直線形的鐵路線。兩城之間還有其他一些停靠站,總站數(shù)為N。各站按照離Ekaterinburg城的距離編號。Ek

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

11、,C3，求出要從起點到終點最少要花多少錢.怎么辦確定題目的當前狀態(tài)與以前狀態(tài)!back第21頁，共74頁，2022年，5月20日，15點16分，星期一買車票當前狀態(tài)以前狀態(tài)當前所在的某個車站這一題的以前狀態(tài)其實只有3種.即滿足3種距離(收費)情況的3個車站.要知道這3個車站可以先做一個預處理.顯然這3個車站在滿足距離限制的條件下應該越遠越好.back第22頁，共74頁，2022年，5月20日，15點16分，星期一買車票預處理 很容易想出一個N2的預處理,但是那樣是會超時的.由于盡量要讓車站離得遠(費用是一樣的啊 )因此在每種收費情況下,每個車站的以前狀態(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點16分，星期一買車票動態(tài)規(guī)劃的部分for i:=be+1 to en do 枚舉當前狀態(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點16分，星期一動規(guī)的要訣狀態(tài)有時候當前狀態(tài)確定后,以前狀態(tài)就已經(jīng)確定,則無需枚舉.back第25頁，共74頁，2022年，5月20日，15點16分，星期一Tom的煩惱Tom是一個非常有創(chuàng)業(yè)精神的人，由于大學學的是汽車制造專業(yè)，所以畢業(yè)后他用有限的資金開了一家汽車零件加工廠， 專門為汽車制造商制造零件。由于資金有限，他只能先購買一臺加工機器。現(xiàn)在他卻遇到了麻煩，多家汽車制造商需要他加 工一些不同零件（由于廠家和零件不同，所以給的加工費也不同），而且不同廠家對于不同零件的

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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