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

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

山東省濰坊第一中學(xué)秦政

clavichord

前言

*動(dòng)態(tài)規(guī)劃是統(tǒng)籌學(xué)的重要內(nèi)容

*動(dòng)態(tài)規(guī)劃是01的重要內(nèi)容

*據(jù)不完全統(tǒng)計(jì)，每次考試動(dòng)態(tài)規(guī)劃起碼有一道題

髡.

前言

*這個(gè)課件的目的：

*對動(dòng)態(tài)規(guī)劃的模型進(jìn)行了一些總結(jié)

*有部分內(nèi)容超出了NOIP范圍

*為同學(xué)們提供一個(gè)刷題的方向

*請同學(xué)們踴躍發(fā)言

動(dòng)忐規(guī)劃的基本概念

*階段

*狀態(tài)

*決策

*狀態(tài)轉(zhuǎn)移

*狀態(tài)轉(zhuǎn)移方程

動(dòng)忐規(guī)劃的基本概念

*最優(yōu)子結(jié)構(gòu)

*無后效性原則

動(dòng)忐規(guī)劃的基本概念

動(dòng)忐規(guī)劃的基本概念

*實(shí)現(xiàn)方式：

*遞推：順推和逆推

*記憶化搜索

*前者靈活，優(yōu)化方法多

*后者可以減少不必要節(jié)點(diǎn)的計(jì)算

動(dòng)忐規(guī)劃的基本概念

*時(shí)間復(fù)雜度：

*狀態(tài)數(shù)*轉(zhuǎn)移費(fèi)用

動(dòng)忐規(guī)劃的模型

*線性模型

*區(qū)間模型

*矩形模型

*樹形模型

*背包模型

*圖狀模型

*SCDP

*多線程DP

*多重DP

*更廣泛的

線性模型

*單線問題：

*上樓梯問題

*LIS問題

*烏龜棋

*詩人小G（簡化版）

*雙線問題：

*LCS問題

*模糊匹配

上樓梯問題

*Zbwmqlw神薜要上樓梯，他一次可以上一層，也可

以兩°

*樓梯有n層

二有多少種上樓梯的方案

上樓梯問題

*N<=10A7?

*設(shè)f[i]表示到第i層得方案數(shù)

*前一步可以上一層也可以上兩層

*F[i]=f[i-i]+f[i-2]

*N<=10A15?

*矩陣乘法

US問題

*給定一個(gè)數(shù)列{an},求它的一個(gè)子序列{bm}

*滿足bi〈b2〈b3<???<bm

*使得m最大

*N<=10000

US問題

*設(shè)f[i]表示以i結(jié)尾的US的長度

*F[i]=max{f[j]]+i,j<iJLa[j]<a[i]

*時(shí)間復(fù)雜度？0（n八2）

*如何優(yōu)化?

US問題

*對于i來說，如果存在一個(gè)長度為len的US以i結(jié)尾,

那么也一定存在長度<len的

*即：滿足單調(diào)性！

*設(shè)g[i]表示的]二i的最小的a[j]

*二分g[k]>=a[i]的最大的k

*F[i]=k+1

*時(shí)間復(fù)雜度O(nlogn)

烏龜棋CN0IP20WtJ

?有一行長度為n+1的格子，編號(hào)。到n+1,要從第。個(gè)

格子的左邊出發(fā)，到達(dá)第n個(gè)格子停止。每次可以向

右移動(dòng)1到4格，分別可以操作G次

?求方案數(shù)

*保證￡七1Q*i=n

?數(shù)據(jù)范圍：n<350,Ct<40

烏龜棋

*F[i][a][b][c][d]表示到位置i,四種操作分別進(jìn)行了

a,b,c,d次

決策有四種

*時(shí)間復(fù)雜度：0(ncA4)

*TLE+MLE

烏龜棋

?=n

*通過a,b,c,d可以推出1

*F[a][b][c][d]

*四種決策

*0(CA4)

詩人小GCNOI2OO9J簡化板

----.JBBBIgjjf

*一首詩包含了若干個(gè)句子，對于一些連續(xù)的短句，’…

可以將它們用空格隔開并放在一行中，注意一行中

可以放的句子數(shù)目是沒有限制的。小G給每首詩定

義了一個(gè)行標(biāo)準(zhǔn)長度（行的長度為一行中符號(hào)的總

個(gè)數(shù)），他希望排版后每行的長度都和行標(biāo)準(zhǔn)長度

相差不遠(yuǎn)。顯然排版時(shí)，不應(yīng)改變原有的句子順序，

并且小G不允許把一個(gè)句子分在兩行或者更多的行

內(nèi)。在滿足上面兩個(gè)條件的情況下，小G對于排版

中的每行定義了一個(gè)不協(xié)調(diào)度,為這行的實(shí)際長度與

行標(biāo)準(zhǔn)長度差值絕對值的P次方，而一個(gè)排版的不協(xié)

調(diào)度為所有行不協(xié)調(diào)度的總和。

*小6最近又作了幾首詩，現(xiàn)在請你對這首詩進(jìn)行排

版，使得排版后的詩盡量協(xié)調(diào)（即不協(xié)調(diào)度盡量

?。雅虐娴慕Y(jié)果告訴他。

詩人小G

*F[i]表示前i句詩的最小不協(xié)調(diào)度

*F[i]=min{f[j]+(sum[i]-sum[j]+i-j-L)Ap)

*時(shí)間復(fù)雜度0(nA2)

*優(yōu)化？

*導(dǎo)數(shù)證明四邊形不等式，有興趣的同學(xué)自己查閱有

關(guān)資料

LCS問題

*給定兩個(gè)字符串S,t

*求最長公共字串

*例：abcde和ace的LCS是ace

*N<=1000

LCS問題

*設(shè)可][口表示第一個(gè)串到i,第二個(gè)串到j(luò)的LCS

*F[i][j]=f[i-1][H]+1,s[i]<j]

*=min{f[i-i][j],f[i][M]},s[i]!=t[j]

*時(shí)間復(fù)雜度0(nA2)

模糊匹配（POJ1229）

*給定兩個(gè)字符串s和t,每個(gè)字符串有英文字母和*?!

組成，*?!的含義分別是：

**:匹配一個(gè)或多個(gè)字符；

*?:匹配至少一個(gè)至多三個(gè)字符；

*!:匹配至少三個(gè)字符。

*問兩個(gè)字符串是否能夠匹配。

*N<=1000

模糊匹配

耒重新定義通配符：

?匹配一個(gè)字符；

*#:匹配一個(gè)字符或者為空；

?$:匹配任意個(gè)字符或者為空。

?那么，題目中的三種通配符，我們可以轉(zhuǎn)化成這樣：

**T@$

??T@##

*!T@@@$

*然后，我們設(shè)了田田表示第一個(gè)字符串的前i個(gè)和第二個(gè)

字符串的前j個(gè)能否匹配，那么，我們可以分情況轉(zhuǎn)移

*與上一道題類似

*時(shí)間復(fù)雜度。（口?）。

區(qū)間模型

*石子歸并

*回文詞

決斗問題

*Blocks

石子歸并

*有n堆石子，第i堆重a[i]

*每次可以合并相鄰兩堆

*合并費(fèi)用為新堆的重量

*求合并成一堆的最小費(fèi)用

*N<=200

石子歸并

*合并的費(fèi)用是一段的和

*設(shè)孔口口]表示合并i到j(luò)的一段

*F[i][j]=min{f[i][k]+f[k+i][j])+sum[i][j]

*時(shí)間復(fù)雜度0(r1A3)

回文詞CI0I2000J

*給定一個(gè)字符串S,要求添加最少的字符，使得s成

為一個(gè)回文串。

*N〈二5。00

回文詞

*abcba:回文

*abcbc:不回文

*表示i到j(luò)變成回文的最小代價(jià)

*F[i][j]<i+1][H],s[i]=s[j]

*=min{f[i+i][j],f[i][j-i]}+i,s[i]!=s[j]

*時(shí)間復(fù)雜度0（n八2）

決斗問題CPOI99J

*1\1個(gè)人排成一圈，他們要決斗N-1場，其中相鄰的兩

人決斗（即第i個(gè)人與第i+1個(gè)人決斗，第N個(gè)人與第1

個(gè)人決斗），死者退出，最終剩下的人勝利。將任

意兩個(gè)人之間決斗的輸贏情況告訴你，決斗順序由

你安排，問哪些人可能成為最終的勝利者？

*N<=200

決斗問題

*首先把環(huán)復(fù)制一份接到后面

*然后一個(gè)人獲勝就是跟自己相遇

*表示i能j相遇

*Meet[i][j]=meet[i][k]&&meet[k][j]&&(beat[i][k]||

beat[j][k])

*時(shí)間復(fù)雜度0(口八3)

BlocksCPOJ139OJ

?現(xiàn)在有一個(gè)長度為n的方塊序列，每個(gè)方塊有一個(gè)顏

色，現(xiàn)在相鄰的相同顏色的方塊可以消除，把長度

為I的方塊消除的得分為求消除所有方塊的最大

得分。

Blocks

*我們可以選擇保留一部分不消除，而跟前面相同顏

色的合并起來一起消除以獲得更大的費(fèi)用，所以再

設(shè)計(jì)狀態(tài)時(shí)，我們需要把后面留下的一起考慮進(jìn)去。

*首先我們把相鄰的相同顏色的縮成一段，len[i]表示

第i段的長度

*記pre[i]表示第i段往前第一個(gè)與i顏色相同的段的編號(hào)

Blocks

*設(shè)小田工燈表示把從第i段到第j段，最后面有長度為k

的與j顏色相同的消去的最大得分

*F[i][j][k]=max[f[i][j-i][o]+(len[j]+k)A2,

*f[>][P^[j]][len[j]+k]+f[pre[j]+i][j][o]]

*記憶化搜索實(shí)現(xiàn)效率高

頭巨形模型

*降維拆成鏈：滑雪

*子矩形：采油區(qū)域

*行列：棋盤分割

*對角線：轉(zhuǎn)紙條

滑雪CSHTSC2002；

*Michael喜歡滑雪這并不奇怪，因?yàn)榛┑拇_很刺激。

可是為了獲得速度，滑的區(qū)域必須向下傾斜，而且

當(dāng)你滑到坡底，你不得不再次走上坡或者等待升降

機(jī)來載你。Michael想知道載一個(gè)區(qū)域中最長的滑坡。

區(qū)域由一個(gè)二維數(shù)組給出。數(shù)組的每個(gè)數(shù)字代表點(diǎn)

的高度。

滑雪

?對于每一個(gè)點(diǎn)，只能轉(zhuǎn)移到更高的地方：

*f[i]Q]+1T砌叫+1/]>h[i]D]X|i-f|+

lj一j'l=1

*所以海拔高度具有很強(qiáng)的階段性。于是我們考慮把

所有的格子取出來，排個(gè)序，這就成了一個(gè)線性的

模型。如果用一個(gè)堆的話實(shí)現(xiàn)起來更簡單。

*時(shí)間復(fù)雜度O(n21ogn2)。

采油區(qū)域CAPIO2OO9J

*Siruseri政府決定將石油資源豐富的Navalur省的土地

拍賣給私人承包商以建立油井。被拍賣的整班土地

為一個(gè)矩形區(qū)域，被劃分為MxN個(gè)小塊。Siruseri地

質(zhì)調(diào)查局有關(guān)于Navalur土地石油儲(chǔ)量的估測數(shù)據(jù)。

這些數(shù)據(jù)表示為MxN個(gè)正整數(shù)，即對每一小塊土地

石油儲(chǔ)量的估計(jì)值。為了避免出現(xiàn)壟斷，政府規(guī)定

每一個(gè)承包商只能承包一個(gè)由KxK塊相連的土地構(gòu)

成的正方形區(qū)域。AoE石油聯(lián)合公司由三個(gè)承包商組

成，他們想選擇三塊互不相交的KxK的區(qū)域使得總

的收益最大。

采油區(qū)域

*一共只有六種情況:

采油區(qū)域

案一共只有上面的六種情況，對于這六種情況，我們

分別要雍護(hù)：

*以某個(gè)點(diǎn)為右上角的矩形內(nèi)的kxk的最大值ru[i][j]

*以某個(gè)點(diǎn)為左上角的矩形內(nèi)的kxk的最大值

*以某個(gè)點(diǎn)為右下角的矩形內(nèi)的kxk的最大值

*以某個(gè)點(diǎn)為左下角的矩形內(nèi)的kxk的最大值

*兩的條豎線之間的kxk的最大值

*兩條橫線之間的kxk的最大值門

采油區(qū)域

*對于前四個(gè)值，我們類似的轉(zhuǎn)移，下面以HJ的轉(zhuǎn)移為例：

*ru[i][j]=

max{ru[i-1][j],ni[i][j-1],sum[i-k+l][j—k+l][i]Q]]

*sum[xl][yl][x2][y2]可以通過子矩形和來0(1)維護(hù)，這樣

維護(hù)這四個(gè)瓦是0(nm)的。

采油區(qū)域

?對于后面兩個(gè)，我們需要記錄每行和每列的ru最大

值r[i]和c[i],會(huì)個(gè)可以在計(jì)算ru的時(shí)候同時(shí)維護(hù)。

cm新rm而強(qiáng)移，也是類似的，這里以cm為例：

*cm[i][j]=max{cm[i]Q-l],c[j])

*這樣我們通過枚舉分割線，利用上面維護(hù)的值就可

以計(jì)算出答案了。時(shí)間復(fù)雜度O(nm)。

棋盤分割（NOI99J

*將一個(gè)8*8的棋盤進(jìn)行如下分割：將原棋盤割下一

塊矩形棋盤并使剩下部分也是矩形，再將剩下的部

分繼續(xù)如此分割，這樣割了n-1次后，連同最后剩下

的矩形棋盤共有n塊矩形棋盤。（每次切割都只能沿

著棋盤格子的邊進(jìn)行。）

允許的分割方案不允許的分割方案.

棋盤分割

?原棋盤上每一格有一個(gè)分值，一塊矩形棋盤的總分

為其所含各格分值之和。現(xiàn)在需要把棋盤按上述規(guī)

則分割成n塊矩形棋盤，并使各矩形棋盤總分的均方

差最小。均方差。=乒3亙，其中平均值

元=卓巖，修為第i塊矩形棋盤的總分。請編程對給

出的矗及n,求出。的最小值。

棋盤分割

*我們從要計(jì)算的值入手。

*我們可以發(fā)現(xiàn)，元的值是一定的。我們把O平方，得

到：a2n=-x)2,我們要使o最小，等價(jià)于

使02rl最小。把。2九展開，得到：

*a2n=￡仁1(蛭-2xtx+x2)=￡21(痣-2%㈤+

x2n

棋盤分割

*于是，我們就要使騫1式靖-2*送)最小。設(shè)

f[i][xl][yl][x2]|y2]裘示把(xl,yl,x2,y2)的矩形分成i份的

(a―24。的最小值，那么：

*f[i][xl][yl][x2][y2]=min{

?f[l][xl][yl][x2]y]+f[i-1][xl]V+I][x2][y2],

*f[i-+f[l][xl][y7+I][x2][y2],

?f[l][xl]|yl][xr][y2]+f[i-l][x7+1][yl][x2][y2],

*f[i-1][xl][yl][xl[y2]+f[l][xf+1][yl][x2][y2]]

?時(shí)間復(fù)雜度0(81)。

傳紙條CNOIP2OO8TJ

?給定一個(gè)nxm的矩形，每個(gè)格子里有一個(gè)數(shù)?，F(xiàn)在

求從左上角到右下角的兩條不相交路徑，使經(jīng)過的

格子的和最大。

傳紙條

?因?yàn)槭窃诰匦卫锏膬蓷l路徑，考慮按照步長劃分階

段。

?我們需要記錄兩條路徑的位置，可以發(fā)現(xiàn)，因?yàn)椴?/p>

長已經(jīng)定了，所以只要知道橫坐標(biāo)，縱坐標(biāo)就可以

推出來。于是，我們設(shè)表示步長為i,第一條

路徑橫坐標(biāo)為j,第二條路徑的橫坐標(biāo)為k的最大和，

因?yàn)閮蓷l路徑可以交換，而這是沒有意義的，所以

我們限定jvk,那么：

傳紙條

*f[Wk]=

max^U-l][j-l][k--l][/][fc],

*f[i-l]U-l][k]J[i-l][j]lk-1])

*上面的方程轉(zhuǎn)移時(shí)要注意判斷兩條路徑不能走到一

塊去和不能走到矩陣外面去。

*時(shí)間復(fù)雜度0(n3)。

樹形模型

*數(shù)值分配型：選課，貪吃的九頭龍

*多叉轉(zhuǎn)二叉

*樹形背包

*位置轉(zhuǎn)移型：CellPhoneNetwork

*鏈劃分型：樹的最長鏈

*可轉(zhuǎn)化成區(qū)間模型和線性模型：加分二叉樹

選課CCTSC99J

*在大學(xué)里每個(gè)學(xué)生，為了達(dá)到一定的學(xué)分，必須從

很多課程里選擇一些課程來學(xué)習(xí)，在課程里有些課

程必須在某些課程之前學(xué)習(xí)，如高等數(shù)學(xué)總是在其

它課程之前學(xué)習(xí)?，F(xiàn)在有N門功課，每門課有個(gè)學(xué)分,

每門課有一門或沒有直接先修課（若課程a是課程b

的先修課即只有學(xué)完了課程a,才能學(xué)習(xí)課程b）o

一個(gè)學(xué)生要從這些課程里選擇M門課程學(xué)習(xí)，問他

能獲得的最大學(xué)分是多少？

*如果要選課程a必須要選課程b,那么就在a和b之間

連邊，這樣，得到的會(huì)是一個(gè)森林。于是我們添加

一個(gè)節(jié)點(diǎn)o,學(xué)分為o,把這個(gè)森林連成樹，于是問

題就是從一顆n+1個(gè)節(jié)點(diǎn)的樹里選m+1個(gè)節(jié)點(diǎn)，使得

總分最大。這樣，點(diǎn)o是必須選的。

*設(shè)￡國[j]表示以i為根的子樹中選j個(gè)的最大得分，那么:

*f[i][j]=max堡裁葡[子f岡3]}

*這個(gè)用樹形背包實(shí)現(xiàn)的話會(huì)異常方便。

*考慮邊界。對于一個(gè)點(diǎn),f[i][O]=O,f[i][l]=w[i],

其余的都是-Infinity。

*時(shí)間復(fù)雜度是0(nm2)的。

貪吃的九頭龍（NOI2OO2）

*傳說中的九頭龍是一種特別貪吃的動(dòng)物。雖然名字

叫“九頭龍”，但這只是說它出生的時(shí)候有九個(gè)頭，

而在成長的過程中，它有時(shí)會(huì)長出很多的新頭，頭

的總數(shù)會(huì)遠(yuǎn)大于九，當(dāng)然也會(huì)有舊頭因衰老而自己

脫落。

*有一天，有M個(gè)腦袋的九頭龍看到一棵長有N個(gè)果子

的果樹，喜出望外，恨不得一口把它全部吃掉?？?/p>

是必須照顧到每個(gè)頭，因此它需要把N個(gè)果子分成M

組，每組至少看一個(gè)果子，讓每個(gè)頭吃一組。

貪吃的九頭龍

*這M個(gè)腦袋中有一個(gè)最大，稱為“大頭”，是眾頭

之首，它要吃掉?。蹚垈€(gè)果子,而且K個(gè)果子中理所

當(dāng)然地應(yīng)該包括唯一的一個(gè)最大的果子。果子由N-1

根樹枝連接起來，由于果樹是一個(gè)整體，因此可以

從任意一個(gè)果子出發(fā)沿著樹枝“走到”任何一個(gè)其

他的果子。

貪吃的九頭龍

*對于每段樹枝，如果它所連接的兩個(gè)果子需要由不

同的頭來吃掉，那么兩個(gè)頭會(huì)共同把樹枝弄斷而把

果子分開；如果這兩個(gè)果子是由同一個(gè)頭來吃掉，

那么這個(gè)頭會(huì)懶得把它弄斷而直接把果子連同樹枝

一起吃掉。當(dāng)然，吃樹枝并不是很舒服的，因此每

段樹枝都有一個(gè)吃下去的“難受值”，而九頭龍的

難受值就是所有頭吃掉的樹枝的“難受值”之和。

*九頭龍希望它的“難受值”盡量小，你能幫它算算

嗎？

貪吃的九頭龍

*首先，如果k+m-l>m,也就是說果子不夠吃，

顯然無解。

*然后來看答案是如何組成的。

?當(dāng)M=2的時(shí)候，難受值的和是大頭吃進(jìn)去的樹枝的

難受值+小頭吃進(jìn)去的難受值

?當(dāng)MN3的時(shí)候，我們把果子按照奇偶分層，讓小頭

們輪流吃就可以保證小頭不會(huì)吃進(jìn)去樹枝，所以這

個(gè)時(shí)候難受值的和是大頭吃進(jìn)去的樹枝的難受值。

*我們以大果子為根建樹，同時(shí)把邊上的權(quán)值推到下

面的節(jié)點(diǎn)上。

貪吃的九頭龍

豪設(shè)表示以i為根的子樹中，大頭吃MSi被小頭吃的裝小值，

表示以i為根的子樹中，大頭吃Msi被大頭吃的最小值，那么：

*f[i]0][O]=min?潦得兒子min[f[k][pfc][O]+xxw[磯f因[pfc][l]}

*f[iJD][l]=min。%鯊鼠子mto{f[對加+w伙]}

*?（0,?n=2

X=-11^>3

*考慮邊界。如果在一個(gè)點(diǎn)大頭不吃，那么顯然是0,所以f[i][0][0]=0；

而如果大頭吃，那么顯然j的值必須是1,所以f[i][l][l]=0。其它的值都

是Infinity。

*時(shí)間復(fù)雜度WnnF）。

貪吃的九頭龍

*我們從多叉轉(zhuǎn)二叉的角度來看這道題

樹的最長鏈

*給定一棵樹，求樹的最長鏈

樹的最長鏈

*貪心做法：兩次BFS

*證明

樹的最長鏈

*動(dòng)態(tài)規(guī)劃：設(shè)f[i]表示兒子連上來的最長鏈，g[i]表示

兒子連上來的次長鏈，h[i]表示父親來的最長鏈

*F[i]=max{f[j]]+1

*同時(shí)更新g[i]

*H[i]=max{f[p],h[p]]+I,f[p]>f[i]+1

*=max[g[p],h[p]}+i,f[p]=f[i]+i

CellPhoneNetworkCPOJ3659J

*給定一^果樹，求樹的最小點(diǎn)支配集。

*N<=10000

*支配集：點(diǎn)覆蓋點(diǎn)

CellPhoneNetwork

*每個(gè)點(diǎn)有三個(gè)狀態(tài)：被兒子覆蓋，選自己，不被兒

子覆蓋。

*設(shè)f［譏0］表示被兒子覆蓋需要的最小點(diǎn)數(shù)，同口］表

示選自己的最小點(diǎn)數(shù)，f［譏2］表示不選自己，不被兒

子覆蓋的最小點(diǎn)數(shù)，那么：

CellPhoneNetwork

*f[i][o]=min{嚷j的兒子f耐min{f[k][o],f[i][1])]

*聞M=￡j是i的兒子min{f[j][o],f[j][i],f[j][2])

f[i][2]=Ej是j的兒子

*這樣的復(fù)雜度是0(n2)的。

CellPhoneNetwork

*這個(gè)方程的瓶頸在第一個(gè)轉(zhuǎn)移上，考慮維護(hù)

sum=￡min{fO][o],f[j][i]},那么：

?f[i][0]=min{sum-min[f[j][0],f[j][1]}+f[j][1]}

*這樣，整個(gè)算法就成0(n)的了。

加分二叉樹CNOIP2OO3J

*設(shè)一個(gè)n個(gè)節(jié)點(diǎn)的二叉樹tree的中序遍歷為（1,2萬,..?刀），

其中數(shù)字1,2,5…,n為節(jié)點(diǎn)編號(hào)。每個(gè)節(jié)點(diǎn)都有一個(gè)分?jǐn)?shù)

（均為正整數(shù)），記第j個(gè)節(jié)點(diǎn)的分?jǐn)?shù)為di,tree及它的每

個(gè)子樹都有一個(gè)務(wù)口分，任一棵子樹subtree（也包含tree

本身）的加分計(jì)算方法如下：

*subtree的左子樹的加分Xsubtree的右子樹的加分十

subtree的根的分?jǐn)?shù)

*若某個(gè)子樹為主，規(guī)定其加分為1,葉子的加分就是葉

節(jié)點(diǎn)本身的分?jǐn)?shù)。不考慮它的空

*子樹。

*試求一棵符合中序遍歷為（i,2,3,..?,n）且加分最高的二

叉樹tree。要求輸出；

*（1）tree的最高加分

*（2）tree的前序遍歷

加分二叉樹

?本題乍一看像是一個(gè)樹形模型，但是樹的形態(tài)又不

確定，不能用樹形模型的方法來做。

*設(shè)幣］［j］表示從i到j(luò)的一段是一棵子樹的最大加分，那

么：

?f[i][j]=max{f[i][k-l]*f[k+l][j]+s[k]]

*時(shí)間復(fù)雜度0(n3)

*第二問：記錄第一問的決策

背包模型

*部分背包

*01背包

*完全背包

*多重背包

*分組背包

*依賴背包

*泛化物品

背包問題

*給定一個(gè)容量為m的背包和n個(gè)物品，每個(gè)物品有一

個(gè)價(jià)值v和一個(gè)費(fèi)用w,求在滿足容量限制的情況下

最大化價(jià)值。

*NPC問題

部分背包問題

*特點(diǎn)：物品可以任意劃分

*方法：求單位價(jià)值，貪心

01背包問題

?特點(diǎn)：每種物品只有一個(gè)，要么取，要么不取

*設(shè)用田]表示前i個(gè)物品，容量為j的最大價(jià)值，很顯然,

每個(gè)物品有取或不取兩種決策：

*f[i][j]=max{f[i-l][j],f[i-l][j-cost[i]]+

value[i]]

*這個(gè)方法時(shí)間復(fù)雜度是O(rnn)的，空間復(fù)雜度是

O(rnn)的。

01背包問題

*空間優(yōu)化：滾動(dòng)數(shù)組

*代碼：

*voidZeroOnePack{

*for(inti=i;i〈=n;i++)

*for(intj=m;j>=cost[i];j-)

*gmax(f[j],f[j-cost[i]]+value[i]);

*)

完全背包問題

*特點(diǎn)：每種物品有無窮多個(gè)

*f[i][j]=max{f[i-l]|j],f[i-l][j-cost[i]]+

value[i],f[i][j—cost[i]]+value[i]}

*代碼：

*voidCompletePack{

*for(inti=i；i<=n;i++)

*for(intj=cost[i];j<=m;j++)

?gmax(f[j],f[j-cost[i]]+value[i]);

*}

多重背包問題

*特點(diǎn)：每類問題有個(gè)數(shù)限制c[i]

*基本想法：每類物品的每一個(gè)看作一個(gè)物品，轉(zhuǎn)化成01

背包

*代碼：

*voidLimitedPack{

*for(inti=i;i〈=n;i++)

*for(intj=i;j<=limit[i];j++)

*for(intk=m;k>=cost[i];k-)

*gmax(f[k],f[k-cost[i]]+value[i]);

*}

多重背包問題

*優(yōu)化：

*二進(jìn)制拆分

*原理：2八k能夠表示出0~2A(k+1>1的所有數(shù)

*把c[i]拆成若干2八k相力口

*O(nmlogc)

分組背包問題

*特點(diǎn)：物品被分為很多組，每組之間有限制。

*假設(shè)限制為：每組只能取一個(gè)

*F[i][j]=max[f[i-i][j],f[i-i][j-w[i][k]]+v[i][k]]

*代碼：

*voidGroupPack{

*for(inti=i;i〈=n;i++)

*for(intj=m;j>=mincost[i];j-)

*for(intk=i;k<=cnt[i];k++)if(cost[i][k]<=j)

*gmax(f[j],f[j-cost[i][k]]+value[i][k];

*}

分配時(shí)間CWFTSC2009TJ

*考試的時(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è)步驟之前同樣需要思考），請

確定自己的策略使得獲得的分?jǐn)?shù)最高。

分配時(shí)間

*每道題實(shí)際上是一個(gè)組。

*我們可以發(fā)現(xiàn)，每個(gè)步驟選或不選對后面的決策是有影

響的，所以我們考慮加一維來區(qū)分。

*設(shè)耳口用小]表示前i道題的前j個(gè)步驟，其中第i道題的第j

個(gè)步驟被選，在k分鐘內(nèi)解決的最大得分，g[i][j][k]表

示前i道題的前j個(gè)步驟，其中第i道題的第j個(gè)步驟不被選,

在k分鐘內(nèi)解決的最大得分，那么：

分配時(shí)間

*f[i][l]M=max{f[i-l][p][k-q-t[i][l]],g[i-l][p][k-

q-t[i][l]}+s[i][l]

?g[i][l][k]=max[f[i-1][p][k],g[i-1][p][k]}

?f[i]D][k]=

max[f[i][j-l][k-t[i][j]]，5[i][/-l][k-q-t[i][/]]}+

s[i][f]

?9[口皿k]=max{f[i][j-l][klg[i][j-l][k]}

?時(shí)間復(fù)雜度O(nmp)。

依賴背包問題

*依賴背包問題，顧名思義，就是一些物品可以選要

建立在其它一些物品被選的基礎(chǔ)之上。這類問題往

往是建立在樹上的，所以通常也叫樹形背包問題。

鑒于在樹形模型中已經(jīng)有了比較詳細(xì)的討論，這里

不再詳細(xì)展開

泛化物品

?背包問題的終極版

*泛化物品是指沒有固定的費(fèi)用和價(jià)值，其價(jià)值是關(guān)

于費(fèi)用的函數(shù)。即：在容量為V的背包問題中，泛化

物品是定義域?yàn)?.,.V的函數(shù)h,當(dāng)其費(fèi)用為V時(shí)，其

價(jià)值為h(v)。

泛化物品

*voidGeneralMatters{

*for(inti=i；i<=n;i++)

*for(intj=m;j>=o;j-)

*for(intk=o;k<=j;k++)

*gmax(f[j],f[j-k]+cost(i,k));

*)

泛化物品

*回顧上面的數(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)易

環(huán)狀模型

*找一個(gè)位置把環(huán)拆成鏈

*DP

*把鏈的首尾接成環(huán)

*枚舉首狀態(tài)

Naptime「POJ2228)

*小尸同學(xué)最近特別累，老是想睡覺

*小F同學(xué)把一天分為n個(gè)時(shí)段，選擇不一定連續(xù)的m

個(gè)時(shí)段來睡覺

*小F同學(xué)睡眠質(zhì)量不好，每次睡覺要花1個(gè)時(shí)段來進(jìn)

入睡眠

*每個(gè)時(shí)段有一個(gè)休息值a[i],如果小F同學(xué)選擇在[l,j]

的時(shí)段內(nèi)睡覺的話,得到的休息就是a[i+i]+...+a[j],

因?yàn)闀r(shí)段i被用來進(jìn)入睡眠了

*如何選擇能夠休息的最好？

*注意天與天是連續(xù)的，即這n個(gè)時(shí)段是一個(gè)環(huán)

naptime

*因?yàn)榄h(huán)首尾相接的地方會(huì)對結(jié)果產(chǎn)生影響，所以要枚舉

開始的狀態(tài)，做幾遍DP

*設(shè)表示前i個(gè)時(shí)間段睡了j段，第i段不睡的最長時(shí)

間，的仃如裝示第i段睡島最長舟面,那么：

*f[i][j][o]=max{f[i-i][j][o],f[M][j][i])

*f[d[i][1]=max{f[i-i][M][o],f[i-i][j-i][i]+t[i]}

*初始時(shí)，所有的f二-INF

*然后枚舉第一個(gè)時(shí)間段睡不睡，分別使

f[l][l][l]=1,f[l][o][o]=l,做兩次DP

*內(nèi)存限制比較緊,要滾動(dòng)

拓?fù)鋱D模型

*邊拓?fù)渑判蜻匘P

*SCC縮點(diǎn)

關(guān)鍵路徑

*給定一個(gè)DAG,求從s到t的最長路

關(guān)鍵路徑

*設(shè)f[i]表示從s到i的最長路徑

*F[i]+dis[i][j]->f[j]

*拓?fù)渑判虻倪^程中解決

最優(yōu)貿(mào)易CNOIP2OO9TJ

*給定一個(gè)圖，邊有的是單向的，有的是雙向的

*有一個(gè)水晶球，每個(gè)點(diǎn)有一個(gè)價(jià)格

*從5出發(fā)到t,沿途在某個(gè)點(diǎn)買入水晶球，在另一個(gè)點(diǎn)

賣出

*顯然你要先買入才能賣出

*最大化收益

最優(yōu)貿(mào)易

*方法一：

*同一個(gè)SCC里的點(diǎn)都可以走到，可以在其中任意一個(gè)

買，任意一個(gè)賣

*收縮SCC,記錄SCC的最大值和最小值

*F[i]表示到i的最大獲利，g[i]表示到i的最小價(jià)格，

minv[i]表示i所在SCC的最小價(jià)格，maxv[i]表示i所在

SCC的最大價(jià)格

*G[i]=min[g[j],minv[i]}

*F[i]=max{f[j],maxv[i]-g[i]]

*邊拓?fù)渑判蜻呑?/p>

最優(yōu)貿(mào)易

*方法二：

*F[i][o]表示到i點(diǎn)，沒有水晶球的最大

*表示到i點(diǎn),有水晶球的最大

*F[i][o]=max{f[j][o],f[j][i]+w[i]]

*f[i][i]=max{f[j]