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

動態(tài)規(guī)劃為了解決一類最優(yōu)化問題通過求得所有子問題的最優(yōu)解來得到最終問題的最優(yōu)解動態(tài)規(guī)劃狀態(tài)狀態(tài)轉(zhuǎn)移方程初始條件動態(tài)規(guī)劃的基本要素狀態(tài)是一維的F[i]由F[j](j<i)得到初始條件F[0]或F[1]Part1線性動態(tài)規(guī)劃設(shè)有整數(shù)序列b1,b2,b3,…,bm，若存在下標i1<i2<i3<…<in，且bi1<bi2<bi3<…<bin，則稱b1,b2,b3,…,bm中有長度為n的上升序列bi1,

bi2,bi3,…,bin

。求最長上升序列的長度N求長度為N的上升序列的個數(shù)求本質(zhì)不同的長度為N的上升序列的個數(shù)N<=1000例1.最長上升序列狀態(tài)：F[i]表示以b[i]結(jié)尾的最長上升序列長度轉(zhuǎn)移方程：F[i]=max(F[j]+1),j<I,b[j]<b[i]初始條件：F[i]=1,1<=i<=NT[i]表示以b[i]結(jié)尾的序列長度為F[i]的方案數(shù)T[i]=sigma(T[j]),F[i]=F[j]+1,B[i]>B[j]初始條件：T[i]=1SolutionP[i]表示上身序列長度為i的序列末尾元素的最小值當計算F[i]時，二分j，滿足P[j]<B[i]F[i]=F[j]+1P[F[i]]=min(P[F[i]],B[i])時間復(fù)雜度：O(NlogN)LISO（NlogN）算法考慮一個由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.zbrka狀態(tài)：F[i][j]表示1～i的一個排列，逆序?qū)?shù)目為j的方案數(shù)枚舉1的位置F[i][j]=sigma(F[i-1][j-k]),0<=k<=i-1時間復(fù)雜度：O(N*N*C)空間復(fù)雜度：O(N*C)Solution如圖，已知一個有向圖，求一條從最左邊的點走到最右邊點的方案（只能從左往右走），使得所經(jīng)過的權(quán)值和除以4的余數(shù)最小。例3.Mod4余數(shù)最小問題狀態(tài)：F[i]表示到點i的最小值轉(zhuǎn)移：F[i]=min((F[j]+num[i])mod4),j到i有邊樣例就出現(xiàn)bugQuestions局部最優(yōu)解不能保證全局最優(yōu)解本題不符合最優(yōu)化性質(zhì)F[i][j]表示到點i余數(shù)為j是否可行求出所有x=(F[k][p]+num[i])%4,F[i][x]=trueSolution狀態(tài)有兩維或者多維F[i][j]表示i~j這個區(qū)間的最優(yōu)值F[i-1][j],F[i][j-1]F[i][j]F[i][k]+F[k][j]F[i][j]

Part2.區(qū)間動態(tài)規(guī)劃在一園形操場四周擺放N堆石子(N≤100),現(xiàn)要將石子有次序地合并成一堆.規(guī)定每次只能選相臨的兩堆合并成一堆,并將新的一堆的石子數(shù),記為該次合并的得分。編一程序,由文件讀入堆數(shù)N及每堆石子數(shù)(≤20), (1)選擇一種合并石子的方案,使得做N-1次合并,得分的總和最少

(2)選擇一種合并石子的方案,使得做N-1次合并,得分的總和最大例4.石子合并Example用data[i,j]表示合并第i～j顆石子的分值狀態(tài)：max[i,j]=max(max[i,k]+max[i+k,j–k]+data[i,k]+data[i+k,j–k])(2<=k<=j)初始條件：max[i,1]=0狀態(tài)：min[i,j]=min(min[i,k]+min[i+k,j–k]+data[i,k]+data[i+k,j–k])(0<=k<=j)初始條件：min[i,0]=0時間復(fù)雜度：O(N^2)Solution在一條馬路上，有一排燈，一個小朋友要去關(guān)燈，如果燈沒有被關(guān)掉，就會每秒造成一定的損失。小朋友一開始在某一個位置，在他左邊和右邊分別有一些燈，給出這些燈和他的距離以及每個燈每秒會造成的損失，求一個方案使得損失最小，輸出最小損失。燈的個數(shù)<=1000例5.關(guān)燈問題關(guān)掉的燈一定是一個連續(xù)的區(qū)間如果路過一個燈但是沒有去關(guān)掉它……設(shè)opt[i][j][0/1]表示區(qū)間[i,j]中的燈都被關(guān)掉之后的最小損失，最后一維表示小朋友的當前位置轉(zhuǎn)移：考慮當前的關(guān)燈操作時間復(fù)雜度：O(N^2)Solutionsubtree的左子樹的加分×subtree的右子樹的加分＋subtree的根的分數(shù)

若某個子樹為主，規(guī)定其加分為1，葉子的加分就是葉節(jié)點本身的分數(shù)。不考慮它的空子樹。

試求一棵符合中序遍歷為（1,2,3,…,n）且加分最高的二叉樹tree。Solution注意到任意一棵子樹的中序遍歷一定是一段連續(xù)的區(qū)間枚舉區(qū)間中的第幾個元素作為這一段區(qū)間的根記f[i][j]表示中序遍歷為[i,j]這個區(qū)間的子樹的最大分數(shù)，g[i]表示第i個點的分數(shù)F[i][j]=max(F[i][k-1]*F[k+1][j]+g[i])初始條件：F[i][j]=0Solution見外部題目描述例8.psolve狀態(tài)：F[i][j]表示i～j在一個月做完的最小所需月份枚舉上一個做了k～i-1轉(zhuǎn)移方程：F[i][j]=min(F[k][i-1]+1),s1[i][j]+s2[k][i-1]<=P,且F[k][i-1]合法初始條件：F[0][0]=1此題寫起來有好多小細節(jié)，建議練習代碼Solution動態(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ī)劃的基本模型狀態(tài)壓縮是一種非常暴力的動態(tài)規(guī)劃，特征也非常明顯，一般適用于數(shù)據(jù)規(guī)模較小的情況。狀態(tài)壓縮復(fù)雜度通常情況下是是指數(shù)級的，編程復(fù)雜度也相對較大。所謂狀態(tài)壓縮，就是把一個比較復(fù)雜的狀態(tài)壓縮為一個數(shù)，通常采用某一種進制的表示方法經(jīng)常通過記憶化搜索來實現(xiàn)Part3.狀態(tài)壓縮動態(tài)規(guī)劃放寒假了，小D終于可以回家了。一個學期之后他有太多的東西想帶回家。小D的背包可以被看作一個4行N列的矩陣，每個物品放入背包的物品恰好需要占據(jù)兩個相鄰的方格，任意兩個物品不能占據(jù)相同的方格。為了充分的利用自己的背包，小D希望背包的所有空間都放置了物品，也就是說，背包中恰好放入了2N個物品。現(xiàn)在小D想知道，不同的放置方案數(shù)有多少種。例9.多米諾骨牌覆蓋搜索？n很大，超時嚴重動態(tài)規(guī)劃？如何表示狀態(tài)？注意到每一列最多只有4行，每一個格子對下一行的影響只有2種：下一行對應(yīng)的格子是否可以和當前格子一起放進一個物品狀態(tài)壓縮！0/1表示每個格子的狀態(tài)，4位二進制數(shù)表示一行的狀態(tài)Solution用F[k][S]來描述一個狀態(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列骨牌的放置方案，不難得到從F[k][u]（u=0…15）到F[k+1][v]（v=0…15）的轉(zhuǎn)移方程。這個過程需要另外寫一個程序去枚舉才能完成。SolutionL盞燈，每盞燈為0/1，表示亮的或暗的有一個叉子有T個叉尖，相鄰兩個叉尖的距離等于相鄰兩盞燈的距離。有些叉尖斷了，用0表示，否則為1叉子對準開關(guān)，可以改變燈的狀態(tài)已知初始燈的狀態(tài)和叉尖狀態(tài)，求叉尖操作的序列使得最后亮著的燈最少L<=50,T<=7例10.xlite同一位置只可能操作一次可以從左到右依次操作F[i][S]表示最后T盞燈燈的狀態(tài)為S時，前i盞燈至少還亮著多少盞S為一個T位