動態(tài)規(guī)劃經(jīng)典教程

31/31動態(tài)規(guī)劃經(jīng)典教程動態(tài)規(guī)劃經(jīng)典教程

引言：本人在做過一些題目后對DP有些感想，就寫了這個總結(jié)：

第一節(jié)動態(tài)規(guī)劃基本概念

一，動態(tài)規(guī)劃三要素：階段，狀態(tài)，決策。

他們的概念到處都是，我就不多說了，我只說說我對他們的理解：

如果把動態(tài)規(guī)劃的求解過程看成一個工廠的生產(chǎn)線，階段就是生產(chǎn)某個商品的不同的環(huán)節(jié)，狀態(tài)就是工件當(dāng)前的形態(tài)，決策就是對工件的操作。顯然不同階段是對產(chǎn)品的一個前面各個狀態(tài)的小結(jié)，有一個個的小結(jié)構(gòu)成了最終的整個生產(chǎn)線。每個狀態(tài)間又有關(guān)聯(lián)（下一個狀態(tài)是由上一個狀態(tài)做了某個決策后產(chǎn)生的）。

下面舉個例子：

要生產(chǎn)一批雪糕，在這個過程中要分好多環(huán)節(jié)：購買牛奶，對牛奶提純處理，放入工廠加工，加工后的商品要包裝，包裝后就去銷售……，這樣沒個環(huán)節(jié)就可以看做是一個階段；產(chǎn)品在不同的時候有不同的狀態(tài)，剛開始時只是白白的牛奶，進(jìn)入生產(chǎn)后做成了各種造型，從冷凍庫拿出來后就變成雪糕（由液態(tài)變成固態(tài)=_=||）。每個形態(tài)就是一個狀態(tài)，那從液態(tài)變成固態(tài)經(jīng)過了冰凍這一操作，這個操作就是一個決策。

一個狀態(tài)經(jīng)過一個決策變成了另外一個狀態(tài)，這個過程就是狀態(tài)轉(zhuǎn)移，用來描述狀態(tài)轉(zhuǎn)移的方程就是狀態(tài)轉(zhuǎn)移方程。

經(jīng)過這個例子相信大家對動態(tài)規(guī)劃有所了解了吧。

下面在說說我對動態(tài)規(guī)劃的另外一個理解：

用圖論知識理解動態(tài)規(guī)劃：把動態(tài)規(guī)劃中的狀態(tài)抽象成一個點(diǎn)，在有直接關(guān)聯(lián)的狀態(tài)間連一條有向邊，狀態(tài)轉(zhuǎn)移的代價就是邊上的權(quán)。這樣就形成了一個有向無環(huán)圖AOE網(wǎng)（為什么無環(huán)呢？往下看）。對這個圖進(jìn)行拓?fù)渑判颍瑒h除一個邊后同時出現(xiàn)入度為0的狀態(tài)在同一階段。這樣對圖求最優(yōu)路徑就是動態(tài)規(guī)劃問題的求解。

二，動態(tài)規(guī)劃的適用范圍

動態(tài)規(guī)劃用于解決多階段決策最優(yōu)化問題，但是不是所有的最優(yōu)化問題都可以用動態(tài)規(guī)劃解答呢？

一般在題目中出現(xiàn)求最優(yōu)解的問題就要考慮動態(tài)規(guī)劃了，但是否可以用還要滿足兩個條件：

最優(yōu)子結(jié)構(gòu)（最優(yōu)化原理）

無后效性

最優(yōu)化原理在下面的最短路徑問題中有詳細(xì)的解答；

什么是無后效性呢？

就是說在狀態(tài)i求解時用到狀態(tài)j而狀態(tài)j就解有用到狀態(tài)k…..狀態(tài)N。

而求狀態(tài)N時有用到了狀態(tài)i這樣求解狀態(tài)的過程形成了環(huán)就沒法用動態(tài)規(guī)劃解答了，這也是上面用圖論理解動態(tài)規(guī)劃中形成的圖無環(huán)的原因。

也就是說當(dāng)前狀態(tài)是前面狀態(tài)的完美總結(jié)，現(xiàn)在與過去無關(guān)。。。

當(dāng)然，有是換一個劃分狀態(tài)或階段的方法就滿足無后效性了，這樣的問題仍然可以用動態(tài)規(guī)劃解。

三，動態(tài)規(guī)劃解決問題的一般思路。

拿到多階段決策最優(yōu)化問題后，第一步要判斷這個問題是否可以用動態(tài)規(guī)劃解決，如果不能就要考慮搜索或貪心了。當(dāng)卻定問題可以用動態(tài)規(guī)劃后，就要用下面介紹的方法解決問題了：（1）模型匹配法：

最先考慮的就是這個方法了。挖掘問題的本質(zhì)，如果發(fā)現(xiàn)問題是自己熟悉的某個基本的模型，就直接套用，但要小心其中的一些小的變動，現(xiàn)在考題辦都是基本模型的變形套用時要小心條件，三思而后行。這些基本模型在先面的分類中將一一介紹。

（2）三要素法

仔細(xì)分析問題嘗試著確定動態(tài)規(guī)劃的三要素，不同問題的卻定方向不同：

先確定階段的問題：數(shù)塔問題，和走路問題（詳見解題報(bào)告）

先確定狀態(tài)的問題：大多數(shù)都是先確定狀態(tài)的。

先確定決策的問題：背包問題。（詳見解題報(bào)告）

一般都是先從比較明顯的地方入手，至于怎么知道哪個明顯就是經(jīng)驗(yàn)問題了，多做題就會發(fā)現(xiàn)。

（3）尋找規(guī)律法：

這個方法很簡單，耐心推幾組數(shù)據(jù)后，看他們的規(guī)律，總結(jié)規(guī)律間的共性，有點(diǎn)貪心的意思。

（4）邊界條件法

找到問題的邊界條件，然后考慮邊界條件與它的領(lǐng)接狀態(tài)之間的關(guān)系。這個方法也很起效。

（5）放寬約束和增加約束

這個思想是在陳啟鋒的論文里看到的，具體內(nèi)容就是給問題增加一些條件或刪除一些條件使問題變的清晰。

第二節(jié)動態(tài)規(guī)劃分類討論

這里用狀態(tài)維數(shù)對動態(tài)規(guī)劃進(jìn)行了分類：

1.狀態(tài)是一維的

1．1下降/非降子序列問題：

問題描述：{挖掘題目的本質(zhì)，一但抽象成這樣的描述就可以用這個方法解}

在一個無序的序列a1,a2,a3,a4…an里，找到一個最長的序列滿足：aiaj>ak…>am,且i>j>k…>m.（最長下降子序列）。

問題分析：

如果前i-1個數(shù)中用到ak(ak>ai或akai(或ajai){最長下降子序列}

實(shí)現(xiàn)求解的部分代碼：

opt[0]:=maxsize；{maxsize為maxlongint或-maxlongint}

fori:=1tondo

forj:=0toi-1do

if(a[j]>a[i])and(opt[j]+1>opt[i])then

opt[i]:=opt[j]+1;

ans:=-maxlongint;

fori:=1tondo

ifopt[i]>ansthenans:=opt[i];{ans為最終解}

復(fù)雜度：從上面的實(shí)現(xiàn)不難看出時間復(fù)雜度為O（N2），空間復(fù)雜度O（N）；

例題1攔截導(dǎo)彈(missile.pas/c/cpp)來源：NOIP1999(提高組)第一題

【問題描述】

某國為了防御敵國的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國的導(dǎo)彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。

輸入導(dǎo)彈依次飛來的高度（雷達(dá)給出的高度數(shù)據(jù)是不大于30000的正整數(shù)），計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈，如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)。

【輸入文件】missile.in

單獨(dú)一行列出導(dǎo)彈依次飛來的高度。

【輸出文件】missile.out

兩行，分別是最多能攔截的導(dǎo)彈數(shù)，要攔截所有導(dǎo)彈最少要配備的系統(tǒng)數(shù)

【輸入樣例】

38920715530029917015865

【輸出樣例】

6

2

【問題分析】

有經(jīng)驗(yàn)的選手不難看出這是一個求最長非升子序列問題，顯然標(biāo)準(zhǔn)算法是動態(tài)規(guī)劃。

以導(dǎo)彈依次飛來的順序?yàn)殡A段，設(shè)計(jì)狀態(tài)opt[i]表示前i個導(dǎo)彈中攔截了導(dǎo)彈i可以攔截最多能攔截到的導(dǎo)彈的個數(shù)。

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

opt[i]=max(opt[j])+1(h[i]>=h[j],0==a[i])and

(opt[j]+1>opt[i])then

opt[i]:=opt[j]+1;

anslen:=0;

fori:=1tondo

ifopt[i]>anslenthen

anslen:=opt[i];

fillchar(opt,sizeof(opt),0);

a[0]:=-maxlongint;

fori:=1tondo

forj:=i-1downto0do

if(a[j](opt[j]+1>opt[i])then

opt[i]:=opt[j]+1;

anstime:=0;

fori:=1tondo

ifopt[i]>anstimethen

anstime:=opt[i];

end;

procedureprint;

begin

writeln(anslen);

writeln(anstime);

close(input);

close(output);

end;

begin

init;

main;

print;

end.

例題二合唱隊(duì)形(chorus.pas/c/cpp)來源：NOIP2004(提高組)第一題

N位同學(xué)站成一排，音樂老師要請其中的(N-K)位同學(xué)出列，使得剩下的K位同學(xué)排成合唱隊(duì)形。

合唱隊(duì)形是指這樣的一種隊(duì)形：設(shè)K位同學(xué)從左到右依次編號為1，2…，K，他們的身高分別為T1，T2，…，TK，則他們的身高滿足T1Ti+1>…>TK(1opt2[i])then

opt2[i]:=opt2[j]+1;

ans:=0;

fori:=1tondo

ifopt1[i]+opt2[i]>ansthen

ans:=opt1[i]+opt2[i];

end;

procedureprint;

begin

writeln(n-ans+1);

close(input);

close(output);

end;

begin

init;

main;

print;

end.

例題3BuyLowBuyLower(buylow.pas/c/cpp)來源:USACO4-3-1

【問題描述】

“逢低吸納”是炒股的一條成功秘訣。如果你想成為一個成功的投資者，就要遵守這條秘訣:

"逢低吸納,越低越買"

這句話的意思是：每次你購買股票時的股價一定要比你上次購買時的股價低.按照這個規(guī)則購買股票的次數(shù)越多越好，看看你最多能按這個規(guī)則買幾次。

給定連續(xù)的N天中每天的股價。你可以在任何一天購買一次股票，但是購買時的股價一定要比你上次購買時的股價低。寫一個程序，求出最多能買幾次股票。

以下面這個表為例,某幾天的股價是:

天數(shù)123456789101112

股價686954646864706778629887

這個例子中,聰明的投資者(按上面的定義)，如果每次買股票時的股價都比上一次買時低，那么他最多能買4次股票。一種買法如下(可能有其他的買法):

天數(shù)25610

股價69686462

【輸入文件】buylow.in

第1行:N(1=a[j],0=opt[i])then

opt[i]:=opt[j]+1;

fori:=1tondo

begin

j:=i-1;

while(j>0)and

((opt[i]1)and

(F[n+1][top]=0)do

dec(top);

write(F[n+1,top]);

fori:=top-1downto1do

begin

m:=F[n+1,i];

whilemD2那么一定會相交，反之則不會相交。

當(dāng)C1>C2時，如果D1Lthenquick(L,j);

ifiopt[i])then

opt[i]:=opt[j]+1;

ans:=-maxlongint;

fori:=1tondo

ifans0)do

begin

init;

main;

read(x,y);

end;

close(input);

close(output);

end.

1.2背包問題

首先說說背包問題的基本模型：

現(xiàn)有N個物品，每個物品的價值為V，重量為W。求用一個載重量為S的背包裝這寫物品，使得所裝物品的總價值最高。

背包問題用貪心和搜索解，當(dāng)然效果不佳，不過在我的貪心和搜索總結(jié)中會說到。顯然標(biāo)準(zhǔn)的解法是動態(tài)規(guī)化，我在解決這個問題時習(xí)慣設(shè)計(jì)一維狀態(tài)，還可以設(shè)計(jì)二維的，二維狀態(tài)在下面會講，現(xiàn)在只討論用一維狀態(tài)實(shí)現(xiàn)背包問題。

背包問題的分類：

(1)小數(shù)背包:物品的重量是實(shí)數(shù)，如油，水等可以取1.67升……

(2)整數(shù)背包：0/1背包：每個物品只能選一次，或不選。不能只選一部分

部分背包：所選物品可以是一部分。

(3)多重背包：背包不只一個。

小數(shù)背包：在貪心總結(jié)中會細(xì)講。

整數(shù)背包：

部分背包：同小數(shù)背包。

0/1背包：這個問題是最經(jīng)常出現(xiàn)的問題，應(yīng)該熟練掌握。

我們先看一下0/1背包的簡化版：

現(xiàn)有N個物品，每個物品重量為W，這些物品能否使在載重量為S的背包裝滿（即重量和正好為S）？如過不能那能使物品重量和最重達(dá)到多少？

針對這一問題我們以物品的個數(shù)分階段，設(shè)計(jì)一個狀態(tài)opt[i]表示載重量為i的背包可否裝滿，顯然opt[i]的基類型是boolean。

決策是什么呢？

當(dāng)要裝第i個物品時，如果前i-1個物品可以使載重為k的背包裝滿，那么載重為k+w[i]的背包就可以裝滿。于是對于一個opt[j]來說，只要opt[j-w[i]]是true（表示可裝滿）那opt[j]就可以裝滿，但要注意：針對每一個物品枚舉背包的載重量時如果這樣正向的推導(dǎo)會使同一個物品用好幾次，因?yàn)閗+w[i]可裝滿那k+w[i]+w[i]就可裝滿，但實(shí)際上是裝不滿的因?yàn)槲锲分挥幸粋€。解決這個問題很簡單，只要逆向推導(dǎo)就

OK了。

這樣劃分階段，設(shè)計(jì)狀態(tài)，滿足無后效性和么？

顯然對與一個每一個階段都是獨(dú)立的，物品的順序并不影響求解，因?yàn)檠b物品的次序不限。而對于opt[j]只考慮opt[j-w[i]]而不考慮后面的，所以滿足無后效性。

有了上面的分析不難寫出狀態(tài)轉(zhuǎn)移方程：

opt[j]:=opt[j-w[1]]{opt[j-w[i]]=true}

時間復(fù)雜度：

階段數(shù)O(S)*狀態(tài)數(shù)（O(N)）*轉(zhuǎn)移代價（O(1)）=O（SN）

下面看幾個例題：

例題5裝箱問題(pack.pas/c/cpp)來源：NOIP2001(普及組)第四題

【問題描述】

有一個箱子容量為V（正整數(shù)，0＜＝V＜＝20000），同時有n個物品（0＜n＜＝30＝，每個物品有一個體積（正整數(shù)）。

要求n個物品中，任取若干個裝入箱內(nèi)，使箱子的剩余空間為最小。

【輸入文件】

第一行一個正整數(shù)V表示箱子的容量，第二行一個正整數(shù)N表示物品個數(shù)，接下來N行列出這N個物品各自的體積。

【輸出文件】

單獨(dú)一行，表示箱子最小的剩余空間。

【輸入樣例】

24

6

8

3

12

7

9

7

【輸出樣例】

【問題分析】

本題是經(jīng)典的0/1背包問題，并且是0/1背包的簡化版，把箱子看做背包，容量看做載重量，體積看做重量，剩余空間最小也就是盡量裝滿背包。于是這個問題便成了：

有一個栽重量為V的背包，有N個物品，盡量多裝物品，使背包盡量的重。

設(shè)計(jì)一個狀態(tài)opt[i]表示重量i可否構(gòu)成。

狀態(tài)轉(zhuǎn)移方程：opt[j]:=opt[j-w[1]]{opt[j-w[i]]=true}

最終的解就是v-x（x0do

begin

inc(top);

a[top]:=m;

inc(tothig,m);

read(m);

end;

fori:=1totopdo

forj:=tothigdownto1do

if(j-a[i]>=0)and

(opt[ii,j-a[i]])then

opt[ii,j]:=true;

end;

ans:=maxhig;

whilenotopt[1,ans]do

dec(ans);

whilenotcan(ans)do

dec(ans);

writeln(ans);

end;

begin

init;

main;

end.

回顧上面的內(nèi)容充分說明動態(tài)規(guī)劃的本質(zhì)就是遞推。其實(shí)按照我的理解（動規(guī)涉及最優(yōu)決策，遞推是單純的總結(jié)）背包問題的簡化版更準(zhǔn)確點(diǎn)算是遞推而非動態(tài)規(guī)劃，至于動歸和遞推之間的界線本來就很模糊（至少我這么認(rèn)為）把它看做什么都可以，沒必要咬文嚼字。

回到0/1背包的原問題上（如果你忘了就去上面看看）。

如果在不知道這個模型的情況下我們怎么做這個題呢？

這就要用到第一節(jié)提到的方法二：三要素法。

題目中明確說明對于一個物品要不就拿走要不就放下，其實(shí)題目赤裸裸的告訴我們決策就是不拿（用0表示）或拿（用1表示）。這樣想都不用想就知道了決策，這也是本題的突破口。知道了決策寫個搜索的程序應(yīng)該是很輕松的了。

那么階段是什么呢？

顯然，給你一堆東西讓你往包里塞，你當(dāng)然是一個一個的那來，塞進(jìn)去。那么階段很明顯就是物品的個數(shù)。

狀態(tài)又是什么呢？

有的人在裝東西是有個習(xí)慣（比如說我）就是先把東西分類，然后把同類的東西打個小包，最后在把小包放進(jìn)去，我們可以按這個思想給物品打一些小包，也就是按照單位為1的遞增的順序準(zhǔn)備好多小包，比如載重是6的包，可以為它準(zhǔn)備載重是1，2，3，4，5的小包。這樣狀態(tài)就可以想出來了：設(shè)計(jì)狀態(tài)opt[i，j]表示裝第i個物品時載重為j的包可以裝到的最大價值。

opt[i-1,j](j-w[i]0)

狀態(tài)轉(zhuǎn)移方程：opt[i,j]=

max{opt[i-1,j],opt[i-1,j-w[i]]+v[i]}(j-w[i]>=0,i>0)

(w[i]:第i個物品的重量，v[i]第i個物品的價值)

解釋：要載重為j的背包空出w[i]（j-w[i]）的空間且裝上第i個物品，比不裝獲得的價值大就裝上它。

邊界條件：opt[0,i]=0;(i∈{1..S})

注：

這種二維的狀態(tài)表示應(yīng)該在下節(jié)講，但是為了方便理解先在這里說了。

上面的方法動態(tài)規(guī)劃三要素都很明顯，實(shí)現(xiàn)也很簡單。但是在我初學(xué)背包時卻用另外一種一維的狀態(tài)表示法。

用第一節(jié)說的思考方法五（放寬約束和增加約束）在重新思考一下這個問題：

怎么放寬約束呢？

把題目中的價值去掉，不考慮價值即最優(yōu)就變成背包問題的簡化版了。那簡化版的求解對我們有何啟示呢？

再一次增加約束：背包只能裝滿。

顯然對于N個裝滿背包的方案中只要找到一個價值最大的就是問題的解。那么裝不滿怎么辦呢？其實(shí)

裝不滿背包，它總要達(dá)到一定的重量（X）。我們可以把這種情況看作是裝滿一個載重為X的小包。

總結(jié)一下上面的思維過程：

放寬約束讓我們找到問題的突破口——和背包問題簡化版一樣，我們可以卻定載重為S的背包是否可以裝滿。

增加約束讓我們找到問題的求解方法——在裝滿背包的方案中選擇最優(yōu)的一個方案。

這樣問題就解決了。

設(shè)計(jì)一個狀態(tài)opt[j]表示裝滿載重為j的背包可獲得的最大價值。對于第i個物品，只要opt[j-w[i]]可以裝滿且opt[j-w[i]]+v[i]比opt[j]大就裝上這個物品（更新opt[j]）。

怎么使opt[j]既有是否構(gòu)成又有最優(yōu)的概念呢？

opt[j]只表示最優(yōu)，只不過使初始條件+1，判斷opt[j]是否為0，如果opt[j]=0說明j裝不滿。

邊界條件：opt[0]=1;

狀態(tài)轉(zhuǎn)移方程：opt[j]=max{opt[j-w[i]]}(0ythenmax:=x

elsemax:=y;

end;

proceduremain;

var

i,j:longint;

begin

fillchar(opt,sizeof(opt),0);

fori:=1tondo

forj:=1totdo

ifj-w[i]0)and

(opt[j-w[i]]+v[i]>opt[j])then

opt[j]:=opt[j-w[i]]+v[i];

ans:=-maxlongint;

fori:=1totdo

ifopt[i]>ansthenans:=opt[i];

end;

procedureprint;

begin

writeln(ans-1);

close(output);

end;

begin

init;

main;

print;

end.

例題9開心的金明來源：NOIP2006（普及組）第二題

【問題描述】

金明今天很開心，家里購置的新房就要領(lǐng)鑰匙了，新房里有一間他自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說：“你的房間需要購買哪些物品，怎么布置，你說了算，只要不超過N元錢就行”。今天一早金明就開始做預(yù)算，但是他想買的東西太多了，肯定會超過媽媽限定的N元。于是，他把每件物品規(guī)定了一個重要度，分為5等：用整數(shù)1~5表示，第5等最重要。他還從因特網(wǎng)上查到了每件物品的價格（都是整數(shù)元）。他希望在不超過N元（可以等于N元）的前提下，使每件物品的價格與重要度的乘積的總和最大。設(shè)第j件物品的價格為v[j]，重要度為w[j]，共選中了k件物品，編號依次為j1...jk，則所求的總和為：v[j1]*w[j1]+..+v[jk]*w[jk]請你幫助金明設(shè)計(jì)一個滿足要求的購物單.

【輸入文件】

輸入的第1行，為兩個正整數(shù)，用一個空格隔開：Nm

（其中N（=0)and

(opt[j-v[i]]>0)and

(opt[j-v[i]]+v[i]*p[i]>opt[j])then

opt[j]:=opt[j-v[i]]+v[i]*p[i];

end;

end;

end;procedureprint;var

i,ans:longint;beginans:=0;

fori:=1tondo

ifopt[i]>ansthen

ans:=opt[i];

writeln(ans-1);

end;

begin

init;

main;

print;

end.

例題10金明的預(yù)算方案(budget.pas/c/cpp)來源：NOIP2006第二題

【問題描述】

金明今天很開心，家里購置的新房就要領(lǐng)鑰匙了，新房里有一間金明自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說：“你的房間需要購買哪些物品，怎么布置，你說了算，只要不超過N元錢就行”。今天一早，金明就開始做預(yù)算了，他把想買的物品分為兩類：主件與附件，附件是從屬于某個主件的，下表就是一些主件與附件的例子：

主件附件

電腦打印機(jī)，掃描儀

書柜圖書

書桌臺燈，文具

工作椅無

如果要買歸類為附件的物品，必須先買該附件所屬的主件。每個主件可以有0個、1個或2個附件。附件不再有從屬于自己的附件。金明想買的東西很多，肯定會超過媽媽限定的N元。于是，他把每件物品規(guī)定了一個重要度，分為5等：用整數(shù)1~5表示，第5等最重要。他還從因特網(wǎng)上查到了每件物品的價格（都是10元的整數(shù)倍）。他希望在不超過N元（可以等于N元）的前提下，使每件物品的價格與重要度的乘積的總和最大。

設(shè)第j件物品的價格為v[j]，重要度為w[j]，共選中了k件物品，編號依次為j1，j2，……，jk，則所求的總和為：

v[j1]*w[j1]+v[j2]*w[j2]+…+v[jk]*w[jk]。（其中*為乘號）

請你幫助金明設(shè)計(jì)一個滿足要求的購物單。

【輸入文件】

輸入文件budget.in的第1行，為兩個正整數(shù)，用一個空格隔開：

Nm（其中N（0說明花i元可以買到物品。這樣就不難設(shè)計(jì)出這個狀態(tài)的轉(zhuǎn)移方程來：

opt[i]=max{opt[i],opt[i-wj]}((i-wj>0)and(opt[i-wj]>0))(0ythenexit(x);

exit(y);

end;

proceduremain;

var

i,j:longint;

begin

fillchar(opt,sizeof(opt),0);

opt[0]:=1;

forj:=1tomdo

fori:=ndowntov[j]do

ifq[j]=0then

begin

if(i-v[j]>=0)and

(opt[i-v[j]]>0)then

opt[i]:=max(opt[i],opt[i-v[j]]

+v[j]*p[j]);

if(i-v[j]-v[q1[j]]>=0)and

(opt[i-v[j]-v[q1[j]]]>0)then

opt[i]:=max(opt[i],opt[i-v[j]-

v[q1[j]]]+v[j]*p[j]+v[q1[j]]*p[q1[

j]]);

if(i-v[j]-v[q2[j]]>=0)and

(opt[i-v[j]-v[q2[j]]]>0)then

opt[i]:=max(opt[i],opt[i-v[j]-

v[q2[j]]]+v[j]*p[j]+v[q2[j]]*p[q2[

j]]);

if(i-v[j]-v[q1[j]]-v[q2[j]]>=0)

and

(opt[i-v[j]-v[q1[j]]-v[q2[j]]]>0)

then

opt[i]:=max(opt[i],opt[i-v[j]-

v[q1[j]]-v[q2[j]]]+v[j]*p[j]+v[q1[j

]]*p[q1[j]]+v[q2[j]]*p[q2[j]]);

ans:=max(ans,opt[i]);

end;

end;

procedureprint;

begin

writeln((ans-1)*10);

close(output);

end;

begin

init;

main;

print;

end.

上面提到的幾個例題都是最基礎(chǔ)的題目，而且把問題抽象后就與背包問題的基本模型一樣了，但有些題目用到了基本模型，要求的解卻不一定很模型一樣，下面看個例子：

例題11MoneySystems(money.pas/c/cpp)來源：USACO2.3

【問題描述】

母牛們不但創(chuàng)建了他們自己的政府而且選擇了建立了自己的貨幣系統(tǒng)。[Intheirownrebelliousway],，他們對貨幣的數(shù)值感到好奇。

傳統(tǒng)地，一個貨幣系統(tǒng)是由1,5,10,20或25,50,和100的單位面值組成的。

母牛想知道有多少種不同的方法來用貨幣系統(tǒng)中的貨幣來構(gòu)造一個確定的數(shù)值。

舉例來說,使用一個貨幣系統(tǒng){1,2,5,10,...}產(chǎn)生18單位面值的一些可能的方法是:18x1,9x2,8x2+2x1,3x5+2+1,等等其它。寫一個程序來計(jì)算有多少種方法用給定的貨幣系統(tǒng)來構(gòu)造一定數(shù)量的面值。保證總數(shù)將會適合longlong(C/C++)和Int64(FreePascal)。

【輸入文件】

貨幣系統(tǒng)中貨幣的種類數(shù)目是V(11then

begin

writeln('-1');

halt;

end;

i:=total;

whilei>0do

begin

ans[path[i]]:=false;

i:=i-w[path[i]];

end;

end;

procedureprint;

var

i:longint;

begin

fori:=1tondo

ifans[i]thenwrite(i,'');

end;

begin

init;

main;

print;

end.

1.3其它問題

一維動態(tài)規(guī)劃最常見的就是前面總結(jié)的最長下降/非降子序列和0/1背包問題了，當(dāng)然還有別的一寫題。由于不是很常見所以沒有固定的解題模式，到時候具體問題具體分析。下面在看一些例子：例題13挖地雷問題(P3.pas/c/cpp)來源：NOIP1996（提高組）第三題（有改動）

【問題描述】

在一個地圖上有N個地窖（N3->4->5

max=27

【Hint】

題目中的路徑是有向的且無環(huán)路（這是我做的改動原題中沒有要求）。

【問題分析】

看到題目的第一影響是貪心——以一點(diǎn)出發(fā)找與他連接的地窖中地雷數(shù)最多的一個。

但很容易想到反例：

5

1211100

1100

010

01

按照貪心答案是3，但實(shí)際上答案是101。

于是就不得不放棄貪心的想法。

但是貪心給了我們啟示：從一個頂點(diǎn)出發(fā)要選擇向一個與他相連且以該點(diǎn)出發(fā)可以挖到較多雷的點(diǎn)走。（有點(diǎn)拗口）

另一種解釋：如果一個頂點(diǎn)連同N個分量，顯然要則一個較大的就是問題的解答，這個定義是滿足最優(yōu)化原理的。

那它滿足無后效性么？

因?yàn)閳D是有向的，所以以與該頂點(diǎn)相連的點(diǎn)在往下走的路線中不包括該點(diǎn)。也就是說圖是一個AOV網(wǎng)（有向無環(huán)圖）。

既然滿足最優(yōu)化原理，且無后效性，我們就可以用動態(tài)規(guī)劃解了。

這個問題的階段就是拓?fù)湫蛄校捎谳斎胧堑谷切?，所以我們沒必要求拓?fù)湫蛄?，只要從N到著求解就可以了。

設(shè)計(jì)狀態(tài)opt[i]表示以i點(diǎn)出發(fā)可以挖到最多的雷的個數(shù)。

狀態(tài)轉(zhuǎn)移方程：opt[i]=max{opt[j]}+w[i](g[i,j]=1)

(g存圖，w[i]存第i個地窖中的雷的個數(shù))。

時間復(fù)雜度：

狀態(tài)數(shù)O(n)*轉(zhuǎn)移代價O(n)=O(n2)

這個題目還要求出路徑，可以用一個輔助數(shù)組path來記錄，path[i]表示從第i個出發(fā)走到的下一個點(diǎn)的編號。求解完只要按path記錄的路徑輸出即可。

【源代碼】

programP3;

const

fin='P3.in';

fout='P3.out';

maxn=200;

var

g:array[0..maxn,0..maxn]oflongint;

n,ans:longint;

w,opt,path:array[0..maxn]of

longint;

procedureinit;

var

i,j:longint;

begin

assign(input,fin);

reset(input);

assign(output,fout);

rewrite(output);

read(n);

fillchar(g,sizeof(g),0);

fori:=1tondo

read(w[i]);

fori:=1tondo

forj:=i+1tondo

read(g[i,j]);

close(input);

end;

proceduremain;

var

i,j:longint;

begin

fillchar(opt,sizeof(opt),0);

fillchar(path,sizeof(path),0);

fori:=ndownto1do

begin

forj:=i+1tondo

if(g[i,j]=1)and(opt[j]>opt[i])then

begin

opt[i]:=opt[j];

path[i]:=j;

end;

inc(opt[i],w[i]);

end;

ans:=1;

fori:=2tondo

ifopt[i]>opt[ans]

thenans:=i;

end;

procedureprint;

var

i:longint;

begin

write(ans);

i:=path[ans];

whilei>0do

begin

write('-->',i);

i:=path[i];

end;

writeln;

writeln('max=',opt[ans]);

close(output);

end;

begin

init;

main;

print;

end.

2.狀態(tài)是二維的

通過前面的學(xué)習(xí)，我想因該對動態(tài)規(guī)劃不陌生了，我學(xué)習(xí)動態(tài)規(guī)劃是沒這么系統(tǒng)，二維，一維一起上。二維狀態(tài)的動態(tài)規(guī)劃是重中之重。

所謂二維狀態(tài)就是說一般設(shè)計(jì)的狀態(tài)是opt[i,j]形式的。那i,j可以代表什么呢？

有很多朋友問過我這個問題，我的回答是：

(1)i,j組合起來代表一個點(diǎn)的坐標(biāo)（顯然是平面坐標(biāo)系）（如：街道問題）。

(2)i,j組合表示一個矩陣的單元的位置（第i行，第j列）（如：數(shù)塔問題）

(3)起點(diǎn)為i長度為j的區(qū)間。（如：回文詞）

(4)起點(diǎn)為i終點(diǎn)為j的區(qū)間。（如：石子合并問題）

(5)兩個沒關(guān)聯(lián)的事物，事物1的第i個位置，對應(yīng)事物2的第j個位置（花店櫥窗設(shè)計(jì)）

(6)兩個序列，第一個序列的前i個位置或第i個位置對應(yīng)第2個序列的第j個位置或前j個位置。（最長公共子序列）。

(7)其它

下面通過例題和基本模型進(jìn)一步說明：

2.1數(shù)塔問題

數(shù)塔問題來源于一道經(jīng)典的IOI的題目，直接說題通過題目總結(jié)公性。以后遇到類似的題目可以參照這個模型。

例題14數(shù)塔問題(numtri.pas/c/cpp)來源：IOI94

【問題描述】

考慮在下面被顯示的數(shù)字金字塔。

寫一個程序來計(jì)算從最高點(diǎn)開始在底部任意處結(jié)束的路徑經(jīng)過數(shù)字的和的最大。每一步可以走到左下方的點(diǎn)也可以到達(dá)右下方的點(diǎn)。

7

38

810

2744

45265

在上面的樣例中,從7到3到8到7到5的路徑產(chǎn)生了最大和:30

【輸入文件】

第一個行包含R(1max)then

max:=opt[i-1,k];

opt[i,j]:=max+a[i,j];

end;

ans:=-maxlongint;

i:=(1+m)div2;

forj:=i-2toi+2do

if(j>0)and(jans)thenans:=opt[n,j];end;procedureprint;beginwriteln(ans);close(input);close(output);end;begininit;main;print;end.

2.2街道問題和數(shù)塔問題一樣街道問題也來源于一道典型的例題，下面我們看一下這道題。

例題16街道問題(way.pas/c/cpp)來源：《奧賽經(jīng)典》（提高篇）

【問題描述】

如圖所示的矩形圖中找到一條從左下角到右上角的最短路徑，圖中數(shù)字表示邊的長度。只能向右或向上走。

【輸入文件】第一行兩個數(shù)，N，M矩形的點(diǎn)有N行M列。（0是X的子序列是指存在一個嚴(yán)格遞增的下標(biāo)序列，使得對于所有j=1,2,…,k有Xij=Zj

例如，序列Z=是序列X=的子序列，相應(yīng)的遞增下標(biāo)序列為。給定兩個序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。例如，若X=和Y=，則序列是X和Y的一個公共子序列，序列也是X和Y的一個公共子序列。而且，后者是X和Y的一個最長公共子序列，因?yàn)閄和Y沒有長度大于4的公共子序列。

給定兩個序列X=和Y=，要求找出X和Y的一個最長公共子序列。

【輸入文件】

輸入文件共有兩行，每行為一個由大寫字母構(gòu)成的長度不超過200的字符串，表示序列X和Y。

【輸出文件】

輸出文件第一行為一個非負(fù)整數(shù)，表示所求得的最長公共子序列的長度，若不存在公共子序列，則輸出文件僅有一行輸出一個整數(shù)0，否則在輸出文件的第二行輸出所求得的最長公共子序列(也用一個大寫字母組成的字符串表示。

【輸入樣例】

ABCBDAB

BDCBA

【輸出樣例】

4

BCBA

【問題分析】

這個問題也是相當(dāng)經(jīng)典的。。

這個題目的階段很不明顯，所以初看這個題目沒什么頭緒，不像前面講的有很明顯的上一步，上一層

之類的東西，只是兩個字符串而且互相沒什么關(guān)聯(lián)。

但仔細(xì)分析發(fā)現(xiàn)還是有入手點(diǎn)的：

既然說是動態(tài)規(guī)劃，那我們首先要考慮的就是怎么劃分子問題，一般對于前面講到的街道問題和數(shù)塔問題涉及走向的，考慮子問題時當(dāng)然是想上一步是什么？但這個問題沒有涉及走向，也沒有所謂的上一步，該怎么辦呢？

既然是求公共子序列，也就有第一個序列的第i個字符和第二個序列的第j個字符相等的情況。

那么我們枚第一個序列（X）的字符，和第二個序列（Y）的字符。

顯然如果X[i]=Y[j]那么起點(diǎn)是1（下面說的子序列都是起點(diǎn)為1的），長度為i的子序列和長度為j的子序列的最長公共子序列就是長度為i-1和長度為j-1的子序列中最長的公共子序列加上X[i]或Y[j]。

那要是不相等呢？

如果不相等，也就是說第一個序列長度為I的子序列和第二個序列中長度為j的子序列的公共子序列中X[i]和Y[j]不同時出現(xiàn)。也就是說第一個序列長度為i的子序列和第二個序列中長度為j的子序列的公共子序列是第一個序列長度為i的子序列和第二個序列中長度為j-1的子序列或第一個序列長度為i-1的子序列和第二個序列中長度為j的子序列的公共子序列中一個更長的。

設(shè)計(jì)一個狀態(tài)opt[i,j]表示起點(diǎn)為1，第一序列長度為i，第二序列長度為j的子序列的最長公共子序列。按照上面的分類就可以得到狀態(tài)轉(zhuǎn)移方程：

opt[i-1,j-1]+x[i](x[i]=y[j])

opt[i,j]=opt[i-1,j]+x[i](length(opt[i-1,j])>=length(opt[i,j-1]))

opt[i,j-1]+y[j](length(opt[i-1,j])=length(opt[i,j-

1])then

opt[i,j]:=opt[i-1,j]

elseopt[i,j]:=opt[i,j-1];

end;

procedureprint;

begin

writeln(length(opt[L1,L2]));

write(opt[L1,L2]);

close(output);

end;

begin

init;

main;

print;

end.

例題18回文詞(palin.pas/c/cpp)來源：IOI2000

【問題描述】

回文詞是一種對稱的字符串——也就是說，一個回文詞，從左到右讀和從右到左讀得到的結(jié)果是一樣的。任意給定一個字符串，通過插入若干字符，都可以變成一個回文詞。你的任務(wù)是寫一個程序，求出將給定字符串變成回文詞所需插入的最少字符數(shù)。

比如字符串“Ab3bd”，在插入兩個字符后可以變成一個回文詞（“dAb3bAd”或“Adb3bdA”）。然而，插入兩個以下的字符無法使它變成一個回文詞。

【輸入文件】

第一行包含一個整數(shù)N，表示給定字符串的長度，3ythenexit(x);

max:=y;

end;

proceduremain;

var

i,x,j,k0,k1:longint;

begin

fillchar(opt,sizeof(opt),0);

readln(n);

readln(a);

b:='';

fori:=ndownto1do

b:=b+a[i];

k0:=0;

k1:=1;

fori:=1tondo

begin

fillchar(opt[k1],sizeof(opt[k1

]),0);

forj:=1tondo

begin

opt[k1,j]:=max(opt[k0,j],opt[

k1,j-1]);

ifa[i]=b[j]then

opt[k1,j]:=max(opt[k1,j],opt[

k0,j-1]+1);

end;

x:=k0;

k0:=k1;

k1:=x;

end;

writeln(n-opt[k0,n]);

end;

begin

main;

end.

用這個方法AC了就該很高興了，但不要停止思考的步伐，還有別的方法么？

從原問題出發(fā)，找這個問題的子問題。和上面說的最長公共子序列問題一樣，設(shè)計(jì)序列的問題我們一般要考慮它的子序列，也就是更短的序列。

這樣就回到了我第一節(jié)說的邊界條件法了。

顯然單獨(dú)的字符就是邊界了，而且單獨(dú)的字符就是回文詞，添加0個字符就可以了。

如果是兩個字符組成的序列怎么辦呢？

只要看他們是否相同就可以了，如果相同那就是回文詞了，添加0個字符，如果不相同就在它的左邊或右邊添一個字符，讓另外一個當(dāng)對稱軸。

如果是3個字符呢？

我們用S存這個序列，如果S[1]=S[3]那么它就是回文詞了,

如果S[1]S[3]那么就在前面添S[3]或后面添S[1]

剩下的就要考慮S[1]S[2]和S[2]S[3]這兩個序列了。

通過前面的分析我們很容易想到這樣的算法：

對于一個序列S只要看它的左右端的字符是否相同，如果相同那么就看除掉兩端字符的新串要添的字符個數(shù)了；如果不同，就在它左面添上右斷的字符然后考慮去掉新序列兩端的字符后的串要添的字符?；蛘咴谟颐嫣砩献蠖说淖址?，在考慮去掉添了字符后新串左右兩端字符得到的新串要添的字符。

設(shè)計(jì)一個二維狀態(tài)opt[L,i]表示長度是L+1，起點(diǎn)是i的序列變成回文詞要添的字符的個數(shù)。階段就是字符的長度，決策要分類，即S[i]和S[i+L]是否相等。

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

min(opt[L-1,i]+1,opt[L-1,i+1]+1)(s[i]s[i+L])

opt[L,i]=

min(opt[L-1,i]+1,opt[L-1,i+1]+1,opt[L-2,i+1])(s[i]=s[i+L])

復(fù)雜度：

空間復(fù)雜度=狀態(tài)數(shù)O（N2）

時間復(fù)雜度=狀態(tài)數(shù)O（N2）*轉(zhuǎn)移代價O（1）=O（N2）

由于空間復(fù)雜度較高，仍然要用滾動數(shù)組。

【源代碼2】

programP1327;

const

maxn=5002;

var

a:array[0..maxn]ofchar;

opt:array[0..2,0..maxn]oflongint;

n,ans:longint;

function

min(x,y:longint):longint;

begin

min:=y;

ifxa[j],10then

begin

if

opt[j-rmb[i],k-rp[i]]+1>opt[j,k]

then

begin

opt[j,k]:=opt[j-rmb[i],k-rp[i]]

+1;

ct[j,k]:=ct[j-rmb[i],k-rp[i]]+ti

me[i];

end

elseif

(opt[j-rmb[i],k-rp[i]]+1=opt[j,k])

and

(ct[j-rmb[i],k-rp[i]]+time[i]maxthenbegin

max:=opt[j,k];ans:=ct[j,k];

end

elseif(opt[j,k]=max)and

(ct[j,k]ans:=ct[j,k];

end;

procedureprint;

begin

writeln(ans);

close(output);

end;

begin

init;

main;

print;

end.

例題21多多看DVD（加強(qiáng)版）(watchdvd.pas/c/cpp)來源：本人原創(chuàng)

【問題描述】

多多進(jìn)幼兒園了，今天報(bào)名了。只有今晚可以好好放松一下了（以后上了學(xué)后會很忙）。她的叔叔決定給他買一些動畫片DVD晚上看?？墒菭敔斠?guī)定他們只能在一定的時間段L看完。

（因?yàn)槭迨暹€要搞NOIP不能太早陪多多看碟，而多多每天很早就困了所以只能在一定的時間段里看碟）。多多列出一張表要叔叔給她買N張DVD碟，大多都是多多愛看的動畫片（福音戰(zhàn)士，機(jī)器貓，火影忍者，櫻桃小丸子……）。這N張碟編號為（1，2，3……N）。多多給每張碟都打了分Mi（Mi>0），打分越高的碟說明多多越愛看。每張碟有播放的時間Ti。多多想在今晚爺爺規(guī)定的時間里看的碟總分最高。（必須把要看的碟看完，也就是說一張碟不能只看一半）。顯然叔叔在買碟是沒必要把N張全買了，只要買要看的就OK了，這樣節(jié)省資金啊。而且多多讓叔叔慣的特別任性只要他看到有幾張就一定會看完。

可是出現(xiàn)了一個奇怪的問題，買碟的地方只買給顧客M（Mythenmax:=x;

end;

proceduremain;

var

i,j,k:longint;

begin

fillchar(opt,sizeof(opt),0);

fori:=1tondo

forj:=mdownto1do

ifj0)or((j=1)

and(k=w[i]))then

opt[j,k]:=max(opt[j-1,k-w[i]]

+val[i],opt[j,k]);

ans:=-maxlongint;

fori:=0tovdo

ifopt[m,i]>ansthen

ans:=opt[m,i];

end;

procedureprint;

begin

write(ans);

close(output);

end;

begin

init;

main;

print;

end.

2.5石子合并問題

也有人把這類問題叫做是區(qū)間上的動態(tài)規(guī)劃。

例題22石子合并(stone.pas/c/cpp)來源：某年NOI（去巴蜀交）

【問題描述】

在一個操場上擺放著一行共n堆的石子?，F(xiàn)要將石子有序地合并成一堆。規(guī)定每次只能選相鄰的兩堆合并成新的一堆，并將新的一堆石子數(shù)記為該次合并的得分。請編輯計(jì)算出將n堆石子合并成一堆的最小得分和將n堆石子合并成一堆的最大得分。

【輸入文件】

輸入第一行為n(nythenmax:=x;

end;

function

min(x,y:longint):longint;

begin

min:=y;

if(x0)then

min:=x;

end;

proceduremain;

var

i,j,L,k:longint;

begin

fillchar(minopt,sizeof(minopt

),200);

fillchar(maxopt,sizeof(maxop

t),0);

fori:=1to2*ndo

minopt[i,i]:=0;

forL:=1ton-1do

fori:=1to2*n-Ldo

begin

j:=i+L;

fork:=itoj-1do

begin

maxopt[i,j]:=max(maxopt[i,j]

,maxopt[i,k]+maxopt[k+1,j]);

minopt[i,j]:=min(minopt[i,j],

minopt[i,k]+minopt[k+1,j]);

end;

inc(maxopt[i,j],sum[j]-sum[i-

1]);

inc(minopt[i,j],sum[j]-sum[i-

1]);

end;

maxans:=-maxlongint;

minans:=maxlongint;

fori:=1tondo

maxans:=max(maxans,maxo

pt[i,i+n-1]);

fori:=1tondo

minans:=min(minans,minopt[

i,i+n-1]);

{fori:=1ton*2do

begin

forj:=1ton*2do

write(maxopt[i,j],'');

writeln;

end;}

end;

begin

init;

main;

writeln(minans,'',maxans);

end.

例題23能量項(xiàng)鏈(energy.pas/c/cpp)來源NOIP2006（提高組）

【問題描述】

在Mars星球上，每個Mars人都隨身佩帶著一串能量項(xiàng)鏈。在項(xiàng)鏈上有N顆能量珠。能量珠是一顆有頭標(biāo)記與尾標(biāo)記的珠子，這些標(biāo)記對應(yīng)著某個正整數(shù)。并且，對于相鄰的兩顆珠子，前一顆珠子的尾標(biāo)記一定等于后一顆珠子的頭標(biāo)記。因?yàn)橹挥羞@樣，通過吸盤（吸盤是Mars人吸收能量的一種器官）的作用，這兩顆珠子才能聚合成一顆珠子，同時釋放出可以被吸盤吸收的能量。如果前一顆能量珠的頭標(biāo)記為m，尾標(biāo)記為r，后一顆能量珠的頭標(biāo)記為r，尾標(biāo)記為n，則聚合后釋放的能量為（Mars單位），新產(chǎn)生的珠子的頭標(biāo)記為m，尾標(biāo)記為n。

需要時，Mars人就用吸盤夾住相鄰的兩顆珠子，通過聚合得到能量，直到項(xiàng)鏈上只剩下一顆珠子為止。顯然，不同的聚合順序得到的總能量是不同的，請你設(shè)計(jì)一個聚合順序，使一串項(xiàng)鏈釋放出的總能量最大。

例如：設(shè)N=4，4顆珠子的頭標(biāo)記與尾標(biāo)記依次為(2，3)(3，5)(5，10)(10，2)⊕

。我們用記號表示兩顆珠子的聚合操作，(jk)表示第j，k兩顆珠子聚合后所釋放的能量。則第4、1兩顆珠子聚合后釋放的能

量為：

(41)=10*2*3=60。

這一串項(xiàng)鏈可以得到最優(yōu)值的一個聚合順序所釋放的總能量為

((41)2)3）=10*2*3+10*3*5+10*5*10=710。

【輸入文件】

輸入文件energy.in的第一行是一個正整數(shù)N（4≤N≤100），表示項(xiàng)鏈上珠子的個數(shù)。第二行是N個用空格隔開的正整數(shù)，所有的數(shù)均不超過1000。第i個數(shù)為第i顆珠子的頭標(biāo)記（1≤i≤N），當(dāng)iythenexit(x);

exit(y);

end;

proceduremain;

var

i,j,k,L:longint;

begin

fillchar(opt,sizeof(opt),0);

forL:=2tondo

fori:=1ton*2-L+1do

begin

j:=i+L;

fork:=i+1toj-1do

opt[i,j]:=max(opt[i,j],opt[i,k]

+opt[k,j]+a[i]*a[j]*a[k]);

end;

fori:=1tondo

ans:=max(ans,opt[i,i+n]);

end;

procedureprint;

begin

writeln(ans);

close(output);

end;

begin

init;

main;

print;

end.

例題24統(tǒng)計(jì)單詞個數(shù)(.pas/c/cpp)來源：NOIP2001（提高組）

【問題描述】

給出一個長度不超過200的由小寫英文字母組成的字母串(約定;該字串以每行20個字母的方式輸入，且保證每行一定為20個)。要求將此字母串分成k份(1opt[n,ans]thenans:=i;

end;

procedure

outputway(i,j:longint);begin

ifi>0then

begin

outputway(i-1,path[i,j]);

write(j,'');

end;

end;

procedureprint;

var

i:longint;

begin

writeln(opt[n,ans]);

outputway(n,ans);

writeln;

end;

begin

init;

main;

print;

end.

例題26Divisibility來源：ZJU2042

【問題描述】

Consideranarbitrarysequenceofintegers.Onecanplace+or-operatorsbetweenintegersinthesequence,thusderivingdifferentarithmeticalexpressionsthatevaluatetodifferentvalues.Letus,forexample,takethesequence:17,5,-21,15.Thereareeightpossibleexpressions:

17+5+-21+15=16

17+5+-21-15=-14

17+5--21+15=58

17+5--21-15=28

17-5+-21+15=6

17-5+-21-15=-24

17-5--21+15=48

17-5--21-15=18

WecallthesequenceofintegersdivisiblebyKif+or-operatorscanbeplacedbetweenintegersinthesequenceinsuchwaythatresultingvalueisdivisiblebyK.Intheaboveexample,thesequenceisdivisibleby7(17+5+-21-15=-14)butisnotdivisibleby5.

Youaretowriteaprogramthatwilldeterminedivisibilityofsequenceofintegers.

譯題：

給出N個數(shù)，你可以在這N個數(shù)中任意地添加+號或-號，求出能不能使算出的結(jié)果被K整除?？梢詣t打印“Divisible”，否則打印“Notdivisible”

(1ythenmax:=x;

end;

proceduremain;

var

i1,i2,j1,j2:longint;

begin

fori1:=1tondo

forj1:=1tondo

fori2:=i1tondo

forj2:=1toj1do

if(i1=i2)and(j1=j2)then

opt[i1,j1,i2,j2]:=opt[i1-1,j1,i2

,j2-1]+a[i1,j1]

elseif(i1=i2-1)and(j1=j2)

then

opt[i1,j1,i2,j2]:=max(opt[i1-1

,j1,i2,j2-1],opt[i1,j1-1,i2,j2-1])

+a[i1,j1]+a[i2,j2]

elseif(i1=i2)and(j1=j2+1)

then

opt[i1,j1,i2,j2]:=max(opt[i1-1

,j1,i2,j2-1],opt[i1-1,j1,i2-1,j2])

+a[i1,j1]+a[i2,j2]

elsebegin

opt[i1,j1,i2,j2]:=max(opt[i1-1

,j1,i2,j2-1],opt[i1-1,j1,i2-1,j2]);

opt[i1,j1,i2,j2]:=max(opt[i1,j

1,i2,j2],opt[i1,j1-1,i2,j2-1]);

opt[i1,j1,i2,j2]:=max(opt[i1,j

1,i2,j2],opt[i1,j1-1,i2-1,j2]);

inc(opt[i1,j1,i2,j2],a[i1,j1]+a[

i2,j2]);

end;

end;

procedureprint;

begin

writeln(opt[n,n,n,n]);

close(output);

end;

begin

init;

main;

print;

end.

如果這個題的數(shù)據(jù)范圍在大點(diǎn)就得優(yōu)化了，怎么優(yōu)化這個程序呢？

上面說過對于時間空間都大的時候，首先想到的就是尋找特點(diǎn)，改變狀態(tài)的表示法，減少狀態(tài)的維數(shù)。

仔細(xì)分析我們發(fā)現(xiàn)，處于同行，同列的狀態(tài)，等價于另外一個點(diǎn)在對角線上的狀態(tài)。而這條對角線正是此題的階段。因?yàn)樵跔顟B(tài)轉(zhuǎn)移的時候后面的哪個點(diǎn)總是從固定的一個方向轉(zhuǎn)移來的。也就是說我們只要對角先上的狀態(tài)就可以省掉那些同行同列的狀態(tài)了。

做過N皇的同學(xué)一定知道怎么表示右上到左下的這幾條對角線，不知道的同學(xué)也沒關(guān)系,對于一個點(diǎn)（i,j）他對角右上角的點(diǎn)就是（i-1，j+1）所以可以看出這些點(diǎn)的和是定值，且值從2到N*2。

這樣用三個變量就可以表示這兩個點(diǎn)了，于是設(shè)計(jì)狀態(tài)opt[k,i1,i2]表示處于階段K時走到i1,i2的兩條路徑所取得的數(shù)的最大和。

用上面的思維不難想出動態(tài)轉(zhuǎn)移方程：

max(opt[k-1,i1-1,i2-1],opt[k-1,i1-1,i2],opt[k-1,i1,i2-1],opt[k-1,i1,i2])+a[i1,k-i1]+a[i2,k-i2](1ythenmax:=x;

end;

proceduremain;

va