1、動(dòng)態(tài)規(guī)劃基礎(chǔ)和建模,山東省濰坊第一中學(xué) 秦政 clavichord,動(dòng)態(tài)規(guī)劃是統(tǒng)籌學(xué)的重要內(nèi)容 動(dòng)態(tài)規(guī)劃是OI的重要內(nèi)容 據(jù)不完全統(tǒng)計(jì)，每次考試動(dòng)態(tài)規(guī)劃起碼有一道題,前言,動(dòng)態(tài)規(guī)劃很重要 ！,這個(gè)課件的目的： 對(duì)動(dòng)態(tài)規(guī)劃的模型進(jìn)行了一些總結(jié) 有部分內(nèi)容超出了NOIP范圍 為同學(xué)們提供一個(gè)刷題的方向 請(qǐng)同學(xué)們踴躍發(fā)言,前言,階段 狀態(tài) 決策 狀態(tài)轉(zhuǎn)移 狀態(tài)轉(zhuǎn)移方程,動(dòng)態(tài)規(guī)劃的基本概念,最優(yōu)子結(jié)構(gòu) 無后效性原則 重疊子問題,動(dòng)態(tài)規(guī)劃的基本概念,DP是一種記憶化的思想,拓展一下： 階段 - 拓?fù)湫?狀態(tài) - 點(diǎn) 狀態(tài)轉(zhuǎn)移 - 邊 決策 - 前驅(qū)？DFA？,動(dòng)態(tài)規(guī)劃的基本概念,DP是狀態(tài)空間上的最短（

2、長）路或者可行路,實(shí)現(xiàn)方式： 遞推：順推和逆推 記憶化搜索 前者靈活，優(yōu)化方法多 后者可以減少不必要節(jié)點(diǎn)的計(jì)算,動(dòng)態(tài)規(guī)劃的基本概念,時(shí)間復(fù)雜度： 狀態(tài)數(shù)*轉(zhuǎn)移費(fèi)用,動(dòng)態(tài)規(guī)劃的基本概念,線性模型 區(qū)間模型 矩形模型 樹形模型 背包模型 圖狀模型 SCDP 多線程DP 多重DP 更廣泛的,動(dòng)態(tài)規(guī)劃的模型,單線問題： 上樓梯問題 LIS問題 烏龜棋 詩人小G（簡化版） 雙線問題： LCS問題 模糊匹配,線性模型,Zbwmqlw神犇要上樓梯，他一次可以上一層，也可以上兩層。 樓梯有n層 有多少種上樓梯的方案,上樓梯問題,N=107？ 設(shè)fi表示到第i層得方案數(shù) 前一步可以上一層也可以上兩層 Fi=fi

3、-1+fi-2 N=1015？ 矩陣乘法,上樓梯問題,給定一個(gè)數(shù)列an，求它的一個(gè)子序列bm 滿足b1b2b3bm 使得m最大 N=10000,LIS問題,設(shè)fi表示以i結(jié)尾的LIS的長度 Fi=maxfj+1,ji且ajai 時(shí)間復(fù)雜度？O(n2) 如何優(yōu)化？,LIS問題,對(duì)于i來說，如果存在一個(gè)長度為len的LIS以i結(jié)尾，那么也一定存在長度=ai的最大的k Fi=k+1 時(shí)間復(fù)雜度O(nlogn),LIS問題,烏龜棋（NOIP2010t）,Fiabcd表示到位置i，四種操作分別進(jìn)行了a,b,c,d次 決策有四種 時(shí)間復(fù)雜度：O(nc4) TLE+MLE,烏龜棋,烏龜棋,一首詩包含了若干個(gè)

4、句子，對(duì)于一些連續(xù)的短句，可以將它們用空格隔開并放在一行中，注意一行中可以放的句子數(shù)目是沒有限制的。小G 給每首詩定義了一個(gè)行標(biāo)準(zhǔn)長度（行的長度為一行中符號(hào)的總個(gè)數(shù)），他希望排版后每行的長度都和行標(biāo)準(zhǔn)長度相差不遠(yuǎn)。顯然排版時(shí)，不應(yīng)改變?cè)械木渥禹樞颍⑶倚?G不允許把一個(gè)句子分在兩行或者更多的行內(nèi)。在滿足上面兩個(gè)條件的情況下，小G 對(duì)于排版中的每行定義了一個(gè)不協(xié)調(diào)度, 為這行的實(shí)際長度與行標(biāo)準(zhǔn)長度差值絕對(duì)值的P 次方，而一個(gè)排版的不協(xié)調(diào)度為所有行不協(xié)調(diào)度的總和。 小G 最近又作了幾首詩，現(xiàn)在請(qǐng)你對(duì)這首詩進(jìn)行排版，使得排版后的詩盡量協(xié)調(diào)（即不協(xié)調(diào)度盡量?。?，并把排版的結(jié)果告訴他。,詩人小G（NO

5、I2009）簡化版,Fi表示前i句詩的最小不協(xié)調(diào)度 Fi=minfj+(sumi-sumj+i-j-L)p 時(shí)間復(fù)雜度O(n2) 優(yōu)化？ 導(dǎo)數(shù)證明四邊形不等式，有興趣的同學(xué)自己查閱有關(guān)資料,詩人小G,給定兩個(gè)字符串s，t 求最長公共字串 例：abcde和ace的LCS是ace N=1000,LCS問題,設(shè)fij表示第一個(gè)串到i，第二個(gè)串到j(luò)的LCS Fij=fi-1j-1+1, si=tj =minfi-1j,fij-1, si!=tj 時(shí)間復(fù)雜度O(n2),LCS問題,給定兩個(gè)字符串s和t，每個(gè)字符串有英文字母和*？！組成，*？！的含義分別是： *：匹配一個(gè)或多個(gè)字符； ？：匹配至少一個(gè)至多

6、三個(gè)字符； ！：匹配至少三個(gè)字符。 問兩個(gè)字符串是否能夠匹配。 N=1000,模糊匹配（POJ1229）,模糊匹配,石子歸并 回文詞 決斗問題 Blocks,區(qū)間模型,有n堆石子，第i堆重ai 每次可以合并相鄰兩堆 合并費(fèi)用為新堆的重量 求合并成一堆的最小費(fèi)用 N=200,石子歸并,合并的費(fèi)用是一段的和 設(shè)fij表示合并i到j(luò)的一段 Fij=minfik+fk+1j+sumij 時(shí)間復(fù)雜度O(n3),石子歸并,給定一個(gè)字符串s，要求添加最少的字符，使得s成為一個(gè)回文串。 N=5000,回文詞（IOI2000）,abcba：回文 abcbc：不回文 Fij表示i到j(luò)變成回文的最小代價(jià) Fij=f

7、i+1j-1, si=sj =minfi+1j,fij-1+1, si!=sj 時(shí)間復(fù)雜度O(n2),回文詞,N個(gè)人排成一圈，他們要決斗N-1場，其中相鄰的兩人決斗（即第i個(gè)人與第i+1個(gè)人決斗，第N個(gè)人與第1個(gè)人決斗），死者退出，最終剩下的人勝利。將任意兩個(gè)人之間決斗的輸贏情況告訴你，決斗順序由你安排，問哪些人可能成為最終的勝利者？ N=200,決斗問題（POI99）,首先把環(huán)復(fù)制一份接到后面 然后一個(gè)人獲勝就是跟自己相遇 Meetij表示i能j相遇 Meetij=meetik i=costi;j-) gmax(fj,fj-costi+valuei); ,01背包問題,完全背包問題,特點(diǎn)：每

8、類問題有個(gè)數(shù)限制ci 基本想法：每類物品的每一個(gè)看作一個(gè)物品，轉(zhuǎn)化成01背包 代碼： void LimitedPack for(int i=1;i=costi;k-) gmax(fk,fk-costi+valuei); ,多重背包問題,優(yōu)化： 二進(jìn)制拆分 原理：2k能夠表示出02(k+1)-1的所有數(shù) 把ci拆成若干2k相加 O(nmlogc),多重背包問題,特點(diǎn)：物品被分為很多組，每組之間有限制。 假設(shè)限制為：每組只能取一個(gè) Fij=maxfi-1j,fi-1j-wik+vik 代碼： void GroupPack for(int i=1;i=mincosti;j-) for(int k=1

9、;k=cnti;k+) if(costik=j) gmax(fj,fj-costik+valueik; ,分組背包問題,考試的時(shí)候合理分配時(shí)間是很重要的，我們應(yīng)該在同樣的時(shí)間內(nèi)盡量得到更多的分?jǐn)?shù)?，F(xiàn)在有m道題需要在n分鐘內(nèi)解決，每道題分為p個(gè)步驟，每道題的每個(gè)步驟都會(huì)有不同的分值，所需時(shí)間也不盡相同?，F(xiàn)在你可以從任意一道題的任意一個(gè)步驟開始，如果當(dāng)前步驟與上一步驟不連續(xù)，則需要q分鐘的思考時(shí)間（每題第一個(gè)步驟之前同樣需要思考），請(qǐng)確定自己的策略使得獲得的分?jǐn)?shù)最高。,分配時(shí)間（WFTSC2009T）,每道題實(shí)際上是一個(gè)組。 我們可以發(fā)現(xiàn)，每個(gè)步驟選或不選對(duì)后面的決策是有影響的，所以我們考慮加一維

10、來區(qū)分。 設(shè)fijk表示前i道題的前j個(gè)步驟，其中第i道題的第j個(gè)步驟被選，在k分鐘內(nèi)解決的最大得分，gijk表示前i道題的前j個(gè)步驟，其中第i道題的第j個(gè)步驟不被選，在k分鐘內(nèi)解決的最大得分，那么：,分配時(shí)間,分配時(shí)間,依賴背包問題，顧名思義，就是一些物品可以選要建立在其它一些物品被選的基礎(chǔ)之上。這類問題往往是建立在樹上的，所以通常也叫樹形背包問題。鑒于在樹形模型中已經(jīng)有了比較詳細(xì)的討論，這里不再詳細(xì)展開,依賴背包問題,泛化物品,void GeneralMatters for(int i=1;i=0;j-) for(int k=0;k=j;k+) gmax(fj,fj-k+cost(i,k)

11、; ,泛化物品,回顧上面的數(shù)值分配型的樹形動(dòng)態(tài)規(guī)劃，考慮其中的一個(gè)節(jié)點(diǎn)i，其子樹就相當(dāng)于一個(gè)一個(gè)的泛化物品，隨著分配給它們的數(shù)值的變化，其價(jià)值也在不斷的變化。由此可見，泛化物品在各個(gè)方面都有著很廣泛的應(yīng)用。,泛化物品,環(huán)狀： Naptime 拓?fù)鋱D： 關(guān)鍵路徑 一般圖模型 最優(yōu)貿(mào)易,圖狀模型,找一個(gè)位置把環(huán)拆成鏈 DP 把鏈的首尾接成環(huán) 枚舉首狀態(tài),環(huán)狀模型,小F同學(xué)最近特別累，老是想睡覺 小F同學(xué)把一天分為n個(gè)時(shí)段，選擇不一定連續(xù)的m個(gè)時(shí)段來睡覺 小F同學(xué)睡眠質(zhì)量不好，每次睡覺要花1個(gè)時(shí)段來進(jìn)入睡眠 每個(gè)時(shí)段有一個(gè)休息值ai，如果小F同學(xué)選擇在I,j的時(shí)段內(nèi)睡覺的話，得到的休息就是ai+1+

12、aj，因?yàn)闀r(shí)段i被用來進(jìn)入睡眠了 如何選擇能夠休息的最好？ 注意天與天是連續(xù)的，即這n個(gè)時(shí)段是一個(gè)環(huán),Naptime（POJ2228）,因?yàn)榄h(huán)首尾相接的地方會(huì)對(duì)結(jié)果產(chǎn)生影響，所以要枚舉開始的狀態(tài)，做幾遍DP 設(shè)fij0表示前i個(gè)時(shí)間段睡了j段，第i段不睡的最長時(shí)間，fij1表示第i段睡的最長時(shí)間，那么： fij0=maxfi-1j0,fi-1j1 fij1=maxfi-1j-10,fi-1j-11+ti 初始時(shí)，所有的f=-INF 然后枚舉第一個(gè)時(shí)間段睡不睡，分別使f111=1,f100=1，做兩次DP 內(nèi)存限制比較緊，要滾動(dòng),naptime,邊拓?fù)渑判蜻匘P SCC縮點(diǎn),拓?fù)鋱D模型,給定一個(gè)

13、DAG，求從s到t的最長路,關(guān)鍵路徑,設(shè)fi表示從s到i的最長路徑 Fi+disij-fj 拓?fù)渑判虻倪^程中解決,關(guān)鍵路徑,給定一個(gè)圖，邊有的是單向的，有的是雙向的 有一個(gè)水晶球，每個(gè)點(diǎn)有一個(gè)價(jià)格 從s出發(fā)到t，沿途在某個(gè)點(diǎn)買入水晶球，在另一個(gè)點(diǎn)賣出 顯然你要先買入才能賣出 最大化收益,最優(yōu)貿(mào)易（NOIP2009T）,方法一： 同一個(gè)SCC里的點(diǎn)都可以走到，可以在其中任意一個(gè)買，任意一個(gè)賣 收縮SCC，記錄SCC的最大值和最小值 Fi表示到i的最大獲利，gi表示到i的最小價(jià)格，minvi表示i所在SCC的最小價(jià)格，maxvi表示i所在SCC的最大價(jià)格 Gi=mingj,minvi Fi=max

14、fj,maxvi-gi 邊拓?fù)渑判蜻呑?最優(yōu)貿(mào)易,方法二： Fi0表示到i點(diǎn)，沒有水晶球的最大 Fi1表示到i點(diǎn)，有水晶球的最大 Fi0=maxfj0,fj1+wi fi1=maxfj1,-wi 前面說過：動(dòng)態(tài)規(guī)劃是狀態(tài)圖的最短路或最長路 嵌套在SPFA算法中，迭代求解,最優(yōu)貿(mào)易,這類問題在NOIP中一般不會(huì)出現(xiàn)，但鑒于在NOIP的模擬題和WFTSC中出現(xiàn)了不止一次，稍微提一下 插頭DP 棋盤DP 集合DP,狀態(tài)壓縮模型,把問題的狀態(tài)壓縮成一個(gè)k進(jìn)制數(shù)來表示，利用這個(gè)數(shù)的每一位反映出來的信息來進(jìn)行轉(zhuǎn)移 問題規(guī)模往往特別小,狀態(tài)壓縮模型,困惑的旅行家（WFTSC2010T）,經(jīng)典的TSP問題 最

15、優(yōu)哈密頓回路 設(shè)fiS表示當(dāng)前在i點(diǎn)，經(jīng)過的點(diǎn)的集合是S FiS=minfjS-i+disji Ans=minfi2n-1+disi1,困惑的旅行家,多線程動(dòng)態(tài)規(guī)劃，顧名思義，就是很多條線一起進(jìn)行的動(dòng)態(tài)規(guī)劃。這類問題要完整的表達(dá)出各條線的特點(diǎn)，轉(zhuǎn)移往往比較簡單。,多線程動(dòng)態(tài)規(guī)劃,一個(gè)公司有三個(gè)移動(dòng)服務(wù)員。如果某個(gè)地方有一個(gè)請(qǐng)求，某個(gè)員工必須趕到那個(gè)地方去（那個(gè)地方?jīng)]有其他員工），某一時(shí)刻只有一個(gè)員工能移動(dòng)。被請(qǐng)求后，他才能移動(dòng)，不允許在同樣的位置出現(xiàn)兩個(gè)員工。從p到q移動(dòng)一個(gè)員工，需要花費(fèi)c(p,q)。這個(gè)函數(shù)沒有必要對(duì)稱，但是c(p,p)=0。公司必須滿足所有 的請(qǐng)求。目標(biāo)是最小化公司花費(fèi)。,Mobile Service（tyvj1061）,Fabc表示三個(gè)員工分別在a,b,c位置上 Fabc-fqbc+caq -faqc+cbq -fabq+ccq F123=0,Mobile Service,你贏得了一場航空公司舉辦的比賽，獎(jiǎng)品是一張加拿大環(huán)游機(jī)票。旅行在這家航空公司開放的最西邊的城市開始，然后一直自西向東旅行，直到你到達(dá)最東邊的城市，再由東向西返回，直到你回到開始的城市。每個(gè)城市只能訪問一次，除了旅行開始的城市之外，這個(gè)城市必定要被訪問兩次（在旅行的開始和結(jié)束）。你不允許使用其他公司的航線或者用其他的交通工具。 給出這個(gè)航空公司開放的城市的列表，和兩兩城市之間