動態(tài)規(guī)劃基礎(chǔ)和建模

1、動態(tài)規(guī)劃基礎(chǔ)和建模第1頁，共105頁，2022年，5月20日，20點45分，星期一動態(tài)規(guī)劃是統(tǒng)籌學(xué)的重要內(nèi)容動態(tài)規(guī)劃是OI的重要內(nèi)容據(jù)不完全統(tǒng)計，每次考試動態(tài)規(guī)劃起碼有一道題前言動態(tài)規(guī)劃很重要 ！第2頁，共105頁，2022年，5月20日，20點45分，星期一這個課件的目的：對動態(tài)規(guī)劃的模型進(jìn)行了一些總結(jié)有部分內(nèi)容超出了NOIP范圍為同學(xué)們提供一個刷題的方向請同學(xué)們踴躍發(fā)言前言第3頁，共105頁，2022年，5月20日，20點45分，星期一階段狀態(tài)決策狀態(tài)轉(zhuǎn)移狀態(tài)轉(zhuǎn)移方程動態(tài)規(guī)劃的基本概念第4頁，共105頁，2022年，5月20日，20點45分，星期一最優(yōu)子結(jié)構(gòu)無后效性原則重疊子問題動態(tài)規(guī)劃的

2、基本概念DP是一種記憶化的思想第5頁，共105頁，2022年，5月20日，20點45分，星期一拓展一下：階段 - 拓?fù)湫驙顟B(tài) - 點狀態(tài)轉(zhuǎn)移 - 邊決策 - 前驅(qū)？DFA？動態(tài)規(guī)劃的基本概念DP是狀態(tài)空間上的最短（長）路或者可行路第6頁，共105頁，2022年，5月20日，20點45分，星期一實現(xiàn)方式：遞推：順推和逆推記憶化搜索前者靈活，優(yōu)化方法多后者可以減少不必要節(jié)點的計算動態(tài)規(guī)劃的基本概念第7頁，共105頁，2022年，5月20日，20點45分，星期一時間復(fù)雜度：狀態(tài)數(shù)*轉(zhuǎn)移費(fèi)用動態(tài)規(guī)劃的基本概念第8頁，共105頁，2022年，5月20日，20點45分，星期一線性模型區(qū)間模型矩形模型樹形模

3、型背包模型圖狀模型SCDP多線程DP多重DP更廣泛的動態(tài)規(guī)劃的模型第9頁，共105頁，2022年，5月20日，20點45分，星期一單線問題：上樓梯問題LIS問題烏龜棋詩人小G（簡化版）雙線問題：LCS問題模糊匹配線性模型第10頁，共105頁，2022年，5月20日，20點45分，星期一Zbwmqlw神犇要上樓梯，他一次可以上一層，也可以上兩層。樓梯有n層有多少種上樓梯的方案上樓梯問題第11頁，共105頁，2022年，5月20日，20點45分，星期一N=107？設(shè)fi表示到第i層得方案數(shù)前一步可以上一層也可以上兩層Fi=fi-1+fi-2N=1015？矩陣乘法上樓梯問題第12頁，共105頁，20

4、22年，5月20日，20點45分，星期一給定一個數(shù)列an，求它的一個子序列bm滿足b1b2b3bm使得m最大N=10000LIS問題第13頁，共105頁，2022年，5月20日，20點45分，星期一設(shè)fi表示以i結(jié)尾的LIS的長度Fi=maxfj+1,ji且ajai時間復(fù)雜度？O(n2)如何優(yōu)化？LIS問題第14頁，共105頁，2022年，5月20日，20點45分，星期一對于i來說，如果存在一個長度為len的LIS以i結(jié)尾，那么也一定存在長度=ai的最大的kFi=k+1時間復(fù)雜度O(nlogn)LIS問題第15頁，共105頁，2022年，5月20日，20點45分，星期一烏龜棋（NOIP2010

5、t）第16頁，共105頁，2022年，5月20日，20點45分，星期一Fiabcd表示到位置i，四種操作分別進(jìn)行了a,b,c,d次決策有四種時間復(fù)雜度：O(nc4)TLE+MLE烏龜棋第17頁，共105頁，2022年，5月20日，20點45分，星期一烏龜棋第18頁，共105頁，2022年，5月20日，20點45分，星期一一首詩包含了若干個句子，對于一些連續(xù)的短句，可以將它們用空格隔開并放在一行中，注意一行中可以放的句子數(shù)目是沒有限制的。小G 給每首詩定義了一個行標(biāo)準(zhǔn)長度（行的長度為一行中符號的總個數(shù)），他希望排版后每行的長度都和行標(biāo)準(zhǔn)長度相差不遠(yuǎn)。顯然排版時，不應(yīng)改變原有的句子順序，并且小 G

6、不允許把一個句子分在兩行或者更多的行內(nèi)。在滿足上面兩個條件的情況下，小G 對于排版中的每行定義了一個不協(xié)調(diào)度, 為這行的實際長度與行標(biāo)準(zhǔn)長度差值絕對值的P 次方，而一個排版的不協(xié)調(diào)度為所有行不協(xié)調(diào)度的總和。小G 最近又作了幾首詩，現(xiàn)在請你對這首詩進(jìn)行排版，使得排版后的詩盡量協(xié)調(diào)（即不協(xié)調(diào)度盡量?。雅虐娴慕Y(jié)果告訴他。詩人小G（NOI2009）簡化版第19頁，共105頁，2022年，5月20日，20點45分，星期一Fi表示前i句詩的最小不協(xié)調(diào)度Fi=minfj+(sumi-sumj+i-j-L)p時間復(fù)雜度O(n2)優(yōu)化？導(dǎo)數(shù)證明四邊形不等式，有興趣的同學(xué)自己查閱有關(guān)資料詩人小G第20頁，共

7、105頁，2022年，5月20日，20點45分，星期一給定兩個字符串s，t求最長公共字串例：abcde和ace的LCS是aceN=1000LCS問題第21頁，共105頁，2022年，5月20日，20點45分，星期一設(shè)fij表示第一個串到i，第二個串到j(luò)的LCSFij=fi-1j-1+1, si=tj =minfi-1j,fij-1, si!=tj時間復(fù)雜度O(n2)LCS問題第22頁，共105頁，2022年，5月20日，20點45分，星期一給定兩個字符串s和t，每個字符串有英文字母和*？！組成，*？！的含義分別是：*：匹配一個或多個字符；？：匹配至少一個至多三個字符；?。浩ヅ渲辽偃齻€字符。問兩

8、個字符串是否能夠匹配。N=1000模糊匹配（POJ1229）第23頁，共105頁，2022年，5月20日，20點45分，星期一模糊匹配第24頁，共105頁，2022年，5月20日，20點45分，星期一石子歸并回文詞決斗問題Blocks區(qū)間模型第25頁，共105頁，2022年，5月20日，20點45分，星期一有n堆石子，第i堆重ai每次可以合并相鄰兩堆合并費(fèi)用為新堆的重量 求合并成一堆的最小費(fèi)用N=200石子歸并第26頁，共105頁，2022年，5月20日，20點45分，星期一合并的費(fèi)用是一段的和設(shè)fij表示合并i到j(luò)的一段Fij=minfik+fk+1j+sumij時間復(fù)雜度O(n3)石子歸并

9、第27頁，共105頁，2022年，5月20日，20點45分，星期一給定一個字符串s，要求添加最少的字符，使得s成為一個回文串。N=5000回文詞（IOI2000）第28頁，共105頁，2022年，5月20日，20點45分，星期一abcba：回文abcbc：不回文Fij表示i到j(luò)變成回文的最小代價Fij=fi+1j-1, si=sj =minfi+1j,fij-1+1, si!=sj時間復(fù)雜度O(n2)回文詞第29頁，共105頁，2022年，5月20日，20點45分，星期一N個人排成一圈，他們要決斗N-1場，其中相鄰的兩人決斗（即第i個人與第i+1個人決斗，第N個人與第1個人決斗），死者退出，最

10、終剩下的人勝利。將任意兩個人之間決斗的輸贏情況告訴你，決斗順序由你安排，問哪些人可能成為最終的勝利者？Nfi+1 =maxgp,hp+1,fp=fi+1樹的最長鏈第62頁，共105頁，2022年，5月20日，20點45分，星期一給定一棵樹，求樹的最小點支配集。N=10000支配集：點覆蓋點Cell Phone Network（POJ3659）第63頁，共105頁，2022年，5月20日，20點45分，星期一Cell Phone Network第64頁，共105頁，2022年，5月20日，20點45分，星期一Cell Phone Network第65頁，共105頁，2022年，5月20日，20點

11、45分，星期一Cell Phone Network第66頁，共105頁，2022年，5月20日，20點45分，星期一 設(shè)一個n個節(jié)點的二叉樹tree的中序遍歷為（l,2,3,n），其中數(shù)字1,2,3,n為節(jié)點編號。每個節(jié)點都有一個分?jǐn)?shù)（均為正整數(shù)），記第j個節(jié)點的分?jǐn)?shù)為di，tree及它的每個子樹都有一個加分，任一棵子樹subtree（也包含tree本身）的加分計算方法如下： subtree的左子樹的加分 subtree的右子樹的加分subtree的根的分?jǐn)?shù) 若某個子樹為主，規(guī)定其加分為1，葉子的加分就是葉節(jié)點本身的分?jǐn)?shù)。不考慮它的空子樹。 試求一棵符合中序遍歷為（1,2,3,n）且加分最高的

12、二叉樹tree。要求輸出； （1）tree的最高加分 （2）tree的前序遍歷加分二叉樹（NOIP2003）第67頁，共105頁，2022年，5月20日，20點45分，星期一加分二叉樹第68頁，共105頁，2022年，5月20日，20點45分，星期一部分背包01背包完全背包多重背包分組背包依賴背包泛化物品背包模型第69頁，共105頁，2022年，5月20日，20點45分，星期一給定一個容量為m的背包和n個物品，每個物品有一個價值v和一個費(fèi)用w，求在滿足容量限制的情況下最大化價值。NPC問題背包問題第70頁，共105頁，2022年，5月20日，20點45分，星期一特點：物品可以任意劃分方法：求單

13、位價值，貪心部分背包問題第71頁，共105頁，2022年，5月20日，20點45分，星期一01背包問題第72頁，共105頁，2022年，5月20日，20點45分，星期一空間優(yōu)化：滾動數(shù)組代碼：void ZeroOnePack for(int i=1;i=costi;j-) gmax(fj,fj-costi+valuei);01背包問題第73頁，共105頁，2022年，5月20日，20點45分，星期一完全背包問題第74頁，共105頁，2022年，5月20日，20點45分，星期一特點：每類問題有個數(shù)限制ci基本想法：每類物品的每一個看作一個物品，轉(zhuǎn)化成01背包代碼：void LimitedPack

14、 for(int i=1;i=n;i+) for(int j=1;j=costi;k-) gmax(fk,fk-costi+valuei);多重背包問題第75頁，共105頁，2022年，5月20日，20點45分，星期一優(yōu)化：二進(jìn)制拆分原理：2k能夠表示出02(k+1)-1的所有數(shù)把ci拆成若干2k相加O(nmlogc)多重背包問題第76頁，共105頁，2022年，5月20日，20點45分，星期一特點：物品被分為很多組，每組之間有限制。假設(shè)限制為：每組只能取一個Fij=maxfi-1j,fi-1j-wik+vik代碼：void GroupPack for(int i=1;i=mincosti;j

15、-) for(int k=1;k=cnti;k+) if(costik=j) gmax(fj,fj-costik+valueik;分組背包問題第77頁，共105頁，2022年，5月20日，20點45分，星期一考試的時候合理分配時間是很重要的，我們應(yīng)該在同樣的時間內(nèi)盡量得到更多的分?jǐn)?shù)?，F(xiàn)在有m道題需要在n分鐘內(nèi)解決，每道題分為p個步驟，每道題的每個步驟都會有不同的分值，所需時間也不盡相同?，F(xiàn)在你可以從任意一道題的任意一個步驟開始，如果當(dāng)前步驟與上一步驟不連續(xù)，則需要q分鐘的思考時間（每題第一個步驟之前同樣需要思考），請確定自己的策略使得獲得的分?jǐn)?shù)最高。分配時間（WFTSC2009T）第78頁，共

16、105頁，2022年，5月20日，20點45分，星期一每道題實際上是一個組。我們可以發(fā)現(xiàn)，每個步驟選或不選對后面的決策是有影響的，所以我們考慮加一維來區(qū)分。設(shè)fijk表示前i道題的前j個步驟，其中第i道題的第j個步驟被選，在k分鐘內(nèi)解決的最大得分，gijk表示前i道題的前j個步驟，其中第i道題的第j個步驟不被選，在k分鐘內(nèi)解決的最大得分，那么：分配時間第79頁，共105頁，2022年，5月20日，20點45分，星期一分配時間第80頁，共105頁，2022年，5月20日，20點45分，星期一 依賴背包問題，顧名思義，就是一些物品可以選要建立在其它一些物品被選的基礎(chǔ)之上。這類問題往往是建立在樹上的

17、，所以通常也叫樹形背包問題。鑒于在樹形模型中已經(jīng)有了比較詳細(xì)的討論，這里不再詳細(xì)展開依賴背包問題第81頁，共105頁，2022年，5月20日，20點45分，星期一泛化物品第82頁，共105頁，2022年，5月20日，20點45分，星期一void GeneralMatters for(int i=1;i=0;j-) for(int k=0;kfj拓?fù)渑判虻倪^程中解決關(guān)鍵路徑第91頁，共105頁，2022年，5月20日，20點45分，星期一給定一個圖，邊有的是單向的，有的是雙向的有一個水晶球，每個點有一個價格從s出發(fā)到t，沿途在某個點買入水晶球，在另一個點賣出顯然你要先買入才能賣出最大化收益最優(yōu)貿(mào)

18、易（NOIP2009T）第92頁，共105頁，2022年，5月20日，20點45分，星期一方法一：同一個SCC里的點都可以走到，可以在其中任意一個買，任意一個賣收縮SCC，記錄SCC的最大值和最小值Fi表示到i的最大獲利，gi表示到i的最小價格，minvi表示i所在SCC的最小價格，maxvi表示i所在SCC的最大價格Gi=mingj,minviFi=maxfj,maxvi-gi邊拓?fù)渑判蜻呑鲎顑?yōu)貿(mào)易第93頁，共105頁，2022年，5月20日，20點45分，星期一方法二：Fi0表示到i點，沒有水晶球的最大Fi1表示到i點，有水晶球的最大Fi0=maxfj0,fj1+wifi1=maxfj1,

19、-wi前面說過：動態(tài)規(guī)劃是狀態(tài)圖的最短路或最長路嵌套在SPFA算法中，迭代求解最優(yōu)貿(mào)易第94頁，共105頁，2022年，5月20日，20點45分，星期一這類問題在NOIP中一般不會出現(xiàn)，但鑒于在NOIP的模擬題和WFTSC中出現(xiàn)了不止一次，稍微提一下插頭DP棋盤DP集合DP狀態(tài)壓縮模型第95頁，共105頁，2022年，5月20日，20點45分，星期一把問題的狀態(tài)壓縮成一個k進(jìn)制數(shù)來表示，利用這個數(shù)的每一位反映出來的信息來進(jìn)行轉(zhuǎn)移問題規(guī)模往往特別小狀態(tài)壓縮模型第96頁，共105頁，2022年，5月20日，20點45分，星期一困惑的旅行家（WFTSC2010T）第97頁，共105頁，2022年，5

20、月20日，20點45分，星期一經(jīng)典的TSP問題最優(yōu)哈密頓回路設(shè)fiS表示當(dāng)前在i點，經(jīng)過的點的集合是SFiS=minfjS-i+disjiAns=minfi2n-1+disi1困惑的旅行家第98頁，共105頁，2022年，5月20日，20點45分，星期一多線程動態(tài)規(guī)劃，顧名思義，就是很多條線一起進(jìn)行的動態(tài)規(guī)劃。這類問題要完整的表達(dá)出各條線的特點，轉(zhuǎn)移往往比較簡單。多線程動態(tài)規(guī)劃第99頁，共105頁，2022年，5月20日，20點45分，星期一一個公司有三個移動服務(wù)員。如果某個地方有一個請求，某個員工必須趕到那個地方去（那個地方?jīng)]有其他員工），某一時刻只有一個員工能移動。被請求后，他才能移動，不允許在同樣的位置出現(xiàn)兩個員工。從p到q移動一個員工，需要花費(fèi)c(p,q)。這個函數(shù)沒有必要對稱，但是c(p,p)=0。公司必須滿足所有 的請求。目標(biāo)是最小化公司花費(fèi)。Mobile Service（tyvj1061）第100頁，共105頁，2022年，5月20