《noip教程動態(tài)規(guī)劃》PPT課件

1、動態(tài)規(guī)劃陳爽1精選PPT為了解決一類最優(yōu)化問題通過求得所有子問題的最優(yōu)解來得到最終問題的最優(yōu)解動態(tài)規(guī)劃2精選PPT狀態(tài)狀態(tài)轉(zhuǎn)移方程初始條件動態(tài)規(guī)劃的基本要素3精選PPT線性動態(tài)規(guī)劃區(qū)間動態(tài)規(guī)劃狀態(tài)壓縮動態(tài)規(guī)劃樹形動態(tài)規(guī)劃動態(tài)規(guī)劃的分類4精選PPT狀態(tài)是一維的Fi 由 Fj (ji) 得到初始條件 F0 或 F1Part 1 線性動態(tài)規(guī)劃5精選PPT設(shè)有整數(shù)序列b1,b2,b3,bm，若存在下標i1i2i3 in，且bi1bi2bi3 bin，則稱 b1,b2,b3,bm中有長度為n的上升序列bi1 , bi2 ,bi3 ,bin 。求最長上升序列的長度N求長度為N的上升序列的個數(shù)求本質(zhì)不同的長

2、度為N的上升序列的個數(shù)N=1000例1.最長上升序列6精選PPT狀態(tài)：Fi表示以bi結(jié)尾的最長上升序列長度轉(zhuǎn)移方程：Fi=max(Fj+1),jI,bjbi初始條件：Fi=1, 1=iBj初始條件：Ti=1Solution7精選PPT本質(zhì)不同？Orderi表示Bi在序列B中是第幾大的Ti=sigma(Tj), 當(dāng)某個orderj1=orderj2時，只累加一個時間復(fù)雜度：O(N2)空間復(fù)雜度：O(N)Solution8精選PPTPi 表示上身序列長度為i的序列末尾元素的最小值當(dāng)計算Fi時，二分j，滿足PjBiFi=Fj+1PFi=min(PFi, Bi)時間復(fù)雜度：O(NlogN)LIS O（

3、NlogN）算法9精選PPT考慮一個由N個整數(shù)構(gòu)成的數(shù)列，其中1到N都在數(shù)列中出現(xiàn)了恰好一次。在這個數(shù)列中從左到右任取兩個數(shù)，如果前者比后者大，那么這對數(shù)就是一個逆序?qū)Α６麄€數(shù)列的逆序數(shù)就是其中所有逆序?qū)Φ目倲?shù)。例如，數(shù)列（1，4，3，2）的逆序數(shù)為3，因為存在三個逆序?qū)Γ海?，3），（4，2）和（3，2）。寫一個程序，計算有多少長度為N的這種數(shù)列，使它的逆序數(shù)恰為C。N=1000,C=10000例2. zbrka10精選PPT狀態(tài)：Fij表示1i的一個排列，逆序?qū)?shù)目為j的方案數(shù)枚舉1的位置Fij=sigma(Fi-1j-k),0=k=i-1時間復(fù)雜度：O(N*N*C)空間復(fù)雜度：O(N*

4、C)Solution11精選PPTFij=Fij-1+Fi-1j-Fi-1j-i第i階段只與第i-1階段有關(guān)滾動數(shù)組，省掉一維時間復(fù)雜度：O(N*C)空間復(fù)雜度：O(C)Solution12精選PPT如圖，已知一個有向圖，求一條從最左邊的點走到最右邊點的方案（只能從左往右走），使得所經(jīng)過的權(quán)值和除以4的余數(shù)最小。例3. Mod 4 余數(shù)最小問題13精選PPT狀態(tài)：Fi表示到點i的最小值轉(zhuǎn)移：Fi=min(Fj+numi) mod 4),j到i有邊樣例就出現(xiàn)bug Questions14精選PPT局部最優(yōu)解不能保證全局最優(yōu)解本題不符合最優(yōu)化性質(zhì)Fij 表示到點i余數(shù)為j是否可行求出所有x=(Fk

5、p+numi)%4,Fix=trueSolution15精選PPTDP不可濫用用之前先考慮是否符合最優(yōu)化原理，并且沒有后效性確定了是DP之后考慮三個基本要素Summary16精選PPT狀態(tài)有兩維或者多維Fij表示ij這個區(qū)間的最優(yōu)值Fi-1j,Fij-1 FijFik + Fkj Fij Part 2.區(qū)間動態(tài)規(guī)劃17精選PPT在一園形操場四周擺放N堆石子(N100),現(xiàn)要將石子有次序地合并成一堆.規(guī)定每次只能選相臨的兩堆合并成一堆,并將新的一堆的石子數(shù),記為該次合并的得分。編一程序,由文件讀入堆數(shù)N及每堆石子數(shù)(20),(1)選擇一種合并石子的方案,使得做N-1次合并,得分的總和最少 (2)

6、 選擇一種合并石子的方案,使得做N-1次合并,得分的總和最大例4. 石子合并18精選PPTExample19精選PPT貪心N=5，石子數(shù)分別為3 4 6 5 4 2用貪心法的合并過程如下：第一次 3 4 6 5 4 2得分 5第二次 5 4 6 5 4得分9第三次 9 6 5 4得分9第四次 9 6 9得分15第五次 15 9得分24第六次24總分：62第一次3 4 6 5 4 2得分 7第二次7 6 5 4 2得分13第三次13 5 4 2得分6第四次13 5 6得分11第五次 13 11得分24第六次24總分：61顯然，貪心法是錯誤的。 20精選PPT用datai,j表示合并第ij顆石子的

7、分值狀態(tài)：maxi,j = max(maxi, k + maxi + k, j k + datai,k + datai+k, jk) (2=k=j)初始條件：maxi,1 = 0狀態(tài)：mini,j = min(mini, k + mini + k, j k + datai,k + datai+k, j k) (0=k=j)初始條件：mini,0 = 0時間復(fù)雜度：O(N2)Solution21精選PPT在一條馬路上，有一排燈，一個小朋友要去關(guān)燈，如果燈沒有被關(guān)掉，就會每秒造成一定的損失。小朋友一開始在某一個位置，在他左邊和右邊分別有一些燈，給出這些燈和他的距離以及每個燈每秒會造成的損失，求一個

8、方案使得損失最小，輸出最小損失。燈的個數(shù)=1000例5. 關(guān)燈問題22精選PPT關(guān)掉的燈一定是一個連續(xù)的區(qū)間如果路過一個燈但是沒有去關(guān)掉它設(shè) optij0/1 表示區(qū)間i,j中的燈都被關(guān)掉之后的最小損失，最后一維表示小朋友的當(dāng)前位置轉(zhuǎn)移：考慮當(dāng)前的關(guān)燈操作時間復(fù)雜度：O(N2)Solution23精選PPT設(shè)一個n個節(jié)點的二叉樹tree的中序遍歷為（l,2,3,n），其中數(shù)字1,2,3,n為節(jié)點編號。每個節(jié)點都有一個分數(shù)（均為正整數(shù)），記第j個節(jié)點的分數(shù)為di，tree及它的每個子樹都有一個加分，任一棵子樹subtree（也包含tree本身）的加分計算方法如下：例6. 加分二叉樹（NOIP20

9、03） 24精選PPTsubtree的左子樹的加分 subtree的右子樹的加分subtree的根的分數(shù) 若某個子樹為主，規(guī)定其加分為1，葉子的加分就是葉節(jié)點本身的分數(shù)。不考慮它的空子樹。 試求一棵符合中序遍歷為（1,2,3,n）且加分最高的二叉樹tree。Solution25精選PPT注意到任意一棵子樹的中序遍歷一定是一段連續(xù)的區(qū)間枚舉區(qū)間中的第幾個元素作為這一段區(qū)間的根記fij表示中序遍歷為i,j這個區(qū)間的子樹的最大分數(shù)，gi表示第i個點的分數(shù)Fij=max(Fik-1*Fk+1j+gi)初始條件：Fij=0Solution26精選PPT給你一個矩陣，其邊長均為整數(shù)。你想把矩陣切割成總數(shù)最

10、少的正方形，其邊長也為整數(shù)。切割工作由一臺切割機器完成，它能沿平行于矩形任一邊的方向，從一邊開始一直切割到另一邊。對得到的矩形再分別進行切割。矩形邊長小于等于100例7. 矩形分割問題27精選PPTFij表示長為i寬為j的矩形所需的最小正方形個數(shù)Fij=min(Fik+Fij-k,Fkj+Fi-kj)Solution28精選PPT見外部題目描述例8. psolve29精選PPT狀態(tài)：Fij表示ij在一個月做完的最小所需月份枚舉上一個做了ki-1轉(zhuǎn)移方程：Fij=min(Fki-1+1), s1ij+s2ki-1=P, 且Fki-1合法初始條件：F00=1此題寫起來有好多小細節(jié)，建議練習(xí)代碼So

11、lution30精選PPT動態(tài)規(guī)劃問題具有以下基本特征： 1、問題具有多階段決策的特征。2、每一階段都有相應(yīng)的“狀態(tài)”與之對應(yīng)，描述狀態(tài)的量稱為“狀態(tài)變量”。3、每一階段都面臨一個決策，選擇不同的決策將會導(dǎo)致下一階段不同的狀態(tài)。4、每一階段的最優(yōu)解問題可以遞歸地歸結(jié)為下一階段各個可能狀態(tài)的最優(yōu)解問題，各子問題與原問題具有完全相同的結(jié)構(gòu)。動態(tài)規(guī)劃的基本模型31精選PPT狀態(tài)壓縮是一種非常暴力的動態(tài)規(guī)劃，特征也非常明顯，一般適用于數(shù)據(jù)規(guī)模較小的情況。狀態(tài)壓縮復(fù)雜度通常情況下是是指數(shù)級的，編程復(fù)雜度也相對較大。所謂狀態(tài)壓縮，就是把一個比較復(fù)雜的狀態(tài)壓縮為一個數(shù)，通常采用某一種進制的表示方法經(jīng)常通過記

12、憶化搜索來實現(xiàn)Part 3. 狀態(tài)壓縮動態(tài)規(guī)劃32精選PPT放寒假了，小D終于可以回家了。一個學(xué)期之后他有太多的東西想帶回家。 小D的背包可以被看作一個4行N列的矩陣，每個物品放入背包的物品恰好需要占據(jù)兩個相鄰的方格，任意兩個物品不能占據(jù)相同的方格。為了充分的利用自己的背包，小D希望背包的所有空間都放置了物品，也就是說，背包中恰好放入了2N個物品。 現(xiàn)在小D想知道，不同的放置方案數(shù)有多少種。 例9. 多米諾骨牌覆蓋33精選PPT搜索？n很大，超時嚴重動態(tài)規(guī)劃？如何表示狀態(tài)？注意到每一列最多只有4行，每一個格子對下一行的影響只有2種：下一行對應(yīng)的格子是否可以和當(dāng)前格子一起放進一個物品狀態(tài)壓縮！0

13、/1表示每個格子的狀態(tài)，4位二進制數(shù)表示一行的狀態(tài)Solution34精選PPT用FkS來描述一個狀態(tài)，這個狀態(tài)表示已經(jīng)把矩陣的前k-1列全部放滿，并且第k列的覆蓋情況為S（s為一個4位二進制數(shù)），此時的擺放方案數(shù)（注意，其實只有S中1的個數(shù)為偶數(shù)時狀態(tài)才有意義，更加深入的探討會發(fā)現(xiàn)需要使用的狀態(tài)很少）。通過枚舉第k列骨牌的放置方案，不難得到從Fku（u = 0 15）到Fk+1v（v = 0 15 ）的轉(zhuǎn)移方程。這個過程需要另外寫一個程序去枚舉才能完成。 Solution35精選PPTL盞燈，每盞燈為0/1，表示亮的或暗的有一個叉子有T個叉尖，相鄰兩個叉尖的距離等于相鄰兩盞燈的距離。有些叉尖斷了，用0表示，否則為1叉子對準開關(guān)，可以改變燈的狀態(tài)已知初始燈的狀態(tài)和叉尖狀態(tài)，求叉尖操作的序列使得最后亮著的燈最少L=50, T=7例10.xlite36精選PPT同一位置只可能操作一次可以從左到右依次操作FiS表示最后T盞燈燈的狀態(tài)