動態(tài)規(guī)劃習(xí)題精講

本文格式為Word版，下載可任意編輯——動態(tài)規(guī)劃習(xí)題精講信息學(xué)競賽中的動態(tài)規(guī)劃專題

哈爾濱工業(yè)大學(xué)周谷越

動態(tài)規(guī)劃動機(jī)狀態(tài)典型題目輔助方法優(yōu)化方法本文針對信息學(xué)競賽（面向中學(xué)生的Noi以及面向大學(xué)生的ACM/ICPC）中的動態(tài)規(guī)劃算法，從動機(jī)入手，探討了動態(tài)規(guī)劃的基本思想和常見應(yīng)用方法。通過一些常見的經(jīng)典題目來歸納動態(tài)規(guī)劃的一般作法并從理論上加以分析和說明。并介紹了一些解決動態(tài)規(guī)劃問題時的一些輔助技巧和優(yōu)化方法。縱觀全文可知，動態(tài)規(guī)劃的關(guān)鍵在于把握本質(zhì)思想的基礎(chǔ)上靈活運(yùn)用。

1.動態(tài)規(guī)劃的動機(jī)和基本思想

1.1.解決重復(fù)子問題1.2.解決繁雜貪心問題2.動態(tài)規(guī)劃狀態(tài)的劃分方法

2.1.一維狀態(tài)劃分

2.2.二維狀態(tài)劃分2.3.樹型狀態(tài)劃分

3.動態(tài)規(guī)劃的輔助與優(yōu)化方法3.1.常見輔助方法3.2.常見優(yōu)化方法4.近年來Noi動態(tài)規(guī)劃題目分析4.1Noi2023璀璨華爾茲4.2Noi2023聰聰與可可4.3Noi2023網(wǎng)絡(luò)收費(fèi)4.4Noi2023千年蟲

附錄參考書籍與相關(guān)材料

信息學(xué)競賽中的動態(tài)規(guī)劃專題

1.動態(tài)規(guī)劃的動機(jī)和基本思想

首先聲明，這里所說的動態(tài)規(guī)劃的動機(jī)是從競賽角度出發(fā)的動機(jī)。

1.1解決重復(fù)子問題對于好多問題，我們利用分治的思想，可以把大問題分解成若干小問題，然后再把各個小問題的答案組合起來，得到大問題的解答。這類問題的共同點(diǎn)是小問題和大問題的本質(zhì)一致。好多分治法可以解決的問題（如quick_sort，hanoi_tower等）都是把大問題化成2個以內(nèi)的不相重復(fù)的小問題，解決的問題數(shù)量即為∑(log2n/k)。而考慮下面這個問題：

USACO1.4.3NumberTriangles22/problem.php?id=1417

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

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

738810274445261

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

第一個行包含R(1F[I-1,J-1]ThenF[I,J]=F[I-1,J]+A[I,J]ElseF[I,J]=F[I-1,J-1]+A[I,J]

接下來我們從理論上來探討使用動態(tài)規(guī)劃的條件。對于一種狀態(tài)劃分的方法來說，狀態(tài)只與狀態(tài)本身的性質(zhì)有關(guān)，而與如何達(dá)到該狀態(tài)等其他條件一概無關(guān)的性質(zhì)叫做無后效性。由于存在無后效性，決策只能從決策本身的性質(zhì)來確定，使得某一階段的狀態(tài)只與它所在階段的前一階段的狀態(tài)有關(guān)?？梢钥闯?，存在無后效性是應(yīng)用動態(tài)規(guī)劃的前提條件。而考慮動態(tài)規(guī)劃的正確性時，問題則需要滿足最優(yōu)子結(jié)構(gòu)。所謂最優(yōu)子結(jié)構(gòu)，即當(dāng)前一階段的狀態(tài)最優(yōu)時，通過狀態(tài)轉(zhuǎn)移方程得到的狀態(tài)也能達(dá)到最優(yōu)。理論上看，無后效性和最優(yōu)子結(jié)構(gòu)是使用動態(tài)規(guī)劃時的兩個基本條件，而具體應(yīng)用動態(tài)規(guī)劃時更多依據(jù)的是經(jīng)驗(yàn)。

下面再引出一道經(jīng)典題目做一下分析：

第2頁/共50頁

信息學(xué)競賽中的動態(tài)規(guī)劃專題

ACM/ICPCShanghai2023Skiing22/problem.php?id=1862

滑雪是一項(xiàng)很受歡迎的體育運(yùn)動，為了獲得速度，滑的區(qū)域必需向下傾斜，而且當(dāng)你滑到坡底，你不得不再次走上坡。我們想知道載一個區(qū)域中最長的滑坡。區(qū)域由一個二維數(shù)組給出。數(shù)組的每個數(shù)字代表點(diǎn)的高度。下面是一個例子：

12345

161718196152425207142322218131211109

我們可以從某個點(diǎn)滑向上下左右相鄰四個點(diǎn)之一，當(dāng)且僅當(dāng)高度減小。在上面的例子中，一條可滑行的滑坡為24-17-16-1。當(dāng)然25-24-23-...-3-2-1更長。事實(shí)上，這是最長的一條。

輸入的第一行表示區(qū)域的行數(shù)R和列數(shù)C(10Then

第3頁/共50頁

信息學(xué)競賽中的動態(tài)規(guī)劃專題

ReturnArr[I,J]IntP,Ans=0ForP=1to4DoIf((I+DX[P],J+DY[P])InMap)And(H[I+DX[P],J+DY[P]]>H[I,J])ThenIf(Ans信息學(xué)競賽中的動態(tài)規(guī)劃專題

思維角度、編程角度還是時空繁雜度角度都明顯優(yōu)于動態(tài)規(guī)劃。

HCPCSpring2023HurdlesRace/hoj/problem/view?id=2476

自從劉翔在雅典奪得110米欄冠軍之后，國人對跨欄比賽的關(guān)注程度大大提高。

阿月和同學(xué)們經(jīng)常在一起探討劉翔需要用多少步來完成比賽，大家對該問題的看法不太一致，經(jīng)常為此整治不休。

我們下面定義這樣一種跨欄比賽：

tl表示起點(diǎn)到終點(diǎn)的距離（可能不是110）；

sl表示劉翔一步可以跨越的最大距離（我們規(guī)定劉翔每次跨越的距離必需是整數(shù)）；fl表示第一個欄到起點(diǎn)的距離（fl信息學(xué)競賽中的動態(tài)規(guī)劃專題

現(xiàn)有一個棱長為n的立方體，可以分成n3個1*1*1的單位立方體。每個單位立方體都有一個整數(shù)值。現(xiàn)在要求在這個立方體找到一個包含完整單位立方體的長方體，使得該長方體內(nèi)所有單位立方體的數(shù)和最大。

第一行包含一個整數(shù)n。接下來n個n2的數(shù)字矩陣，每個數(shù)字矩陣代表一層，每個數(shù)字代表一個單位立方體的整數(shù)值。

輸出僅包括最大的長方體的數(shù)和。

21221-1–2-2-1

6最基礎(chǔ)的方法是“直譯〞枚舉過程，時間繁雜度O（n9）。而記錄從前考察的結(jié)果。如下圖，在統(tǒng)計(jì)長方體2時，只要將長方體1的統(tǒng)計(jì)結(jié)果加上長方體3就可以了，而不必按上述算法那樣重新進(jìn)行計(jì)算。經(jīng)過這樣的優(yōu)化，利用了前面的計(jì)算結(jié)果，時間繁雜度降為O（n8）。而對于每個平面的矩形有一種經(jīng)典的壓縮方法，設(shè)rec[x,y,z]表示z軸坐標(biāo)為z的水平面中矩形（1,1,x,y）的數(shù)和。則z軸坐標(biāo)為z的水平面中左上角為（x1,y1）、右下角為（x2,y2）的矩陣的數(shù)和為rec[x2,y2,z]+rec[x1,y1,z]-rec[x2,y1,z]-rec[x1,y2,z]。有了上面的關(guān)系式，我們下面要做的只是枚舉z,x1,x2,y1,y2來查找最優(yōu)解。對于每組固定的x1,x2,y1,y2，rec[z,x1,x2,y1,y2]就等于z個數(shù)字，那么只要求它們的最大連續(xù)和就可以?？偟臅r間繁雜度為O（n5）。

Noip2023合唱隊(duì)型

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

合唱隊(duì)形是指這樣的一種隊(duì)形：設(shè)K位同學(xué)從左到右依次編號為1，2?，K，他們的

第10頁/共50頁

信息學(xué)競賽中的動態(tài)規(guī)劃專題

身高分別為T1，T2，?，TK，則他們的身高滿足T1Ti+1>?>TK（1≤i≤K）。

你的任務(wù)是，已知所有N位同學(xué)的身高，計(jì)算最少需要幾位同學(xué)出列，可以使得剩下的同學(xué)排成合唱隊(duì)形。

第一行是一個整數(shù)N(2≤N≤106)，表示同學(xué)的總數(shù)。第一行有n個整數(shù)，用空格分隔，第i個整數(shù)Ti(130≤Ti≤230)是第i位同學(xué)的身高(厘米)。

只包含一個整數(shù)，就是最少需要幾位同學(xué)出列。

8

186186150200160130197220

4首先只考慮左半部分的合唱隊(duì)型，這種題目類型叫做最長上升子序列問題（LIS），最常規(guī)的算法是設(shè)F[I]表示前I個數(shù)字中（必需包含A[I]）的最長上升子序列的長度，狀態(tài)轉(zhuǎn)移方程為F[I]=Max{F[J]+1}，其中J∈[0,I-1]且A[J]N0時，n可以由若干S到T之間的正整數(shù)（包括S，T）組成。因此，將障礙點(diǎn)按升序排列，當(dāng)兩相鄰障礙點(diǎn)之間距離較大時，可適當(dāng)縮小兩障礙點(diǎn)之間距離，但不影響最終結(jié)果。（特別地，當(dāng)S=T時需要單獨(dú)處理）

針對每一組S和T都存在一個N0。對于任意的S和T（S≠T時），那么每次至少有T和T-1兩種跳法。假設(shè)青蛙跳T次，其中K次跳T步，T-K次跳T-1步，那么總步數(shù)為KT+(T-K)(T-1)=T(T-1)+K，也就是說T(T-1)以外的所有點(diǎn)都可以跳到。這樣一來，我們就可以把間距超過T(T-1)+K的兩點(diǎn)間距離化為T(T-1)+K。T=K=10時，T(T-1)+K取得最大值100，這時整個算法的時間繁雜度為O(100MT)，可以在1s內(nèi)通過全部測試數(shù)據(jù)。

2.1.3一維狀態(tài)劃分的非線性動態(tài)規(guī)劃

下面要探討的是一維狀態(tài)劃分的非線性動態(tài)規(guī)劃問題。其中最為經(jīng)典的模型就是0-1背包問題：給定N種物品和一背包。物品I的重量是WI，其價值為VI，背包的容量為C。選擇裝入背包的物品，使得裝入背包中物品的總價值最大，求這個最大價值。

每考慮一件物品為一個階段，對于每一物品來說，都只有取和不取兩種可能。那么設(shè)F[I,J]表示考慮前I個物品取的總重量不超過J的最大價值，則有狀態(tài)轉(zhuǎn)移方程：F[I,J]=Max（F[I-1,J],F[I-1,J-WI]+VI）。實(shí)際上，0-1背包問題和NumberTriangles問題只是在做決策時略有不同，前者考慮取或者不取，而后者考慮要走到左邊還是右邊。最終提醒一下，0-1背包是一個NP問題，時空繁雜度均為O（NW），當(dāng)W的規(guī)模比較大時（不是很過分的大），空間開銷隨之增大，我們可以利用滾動數(shù)組解決這一問題。由于動態(tài)規(guī)劃的無后效性，我們只需記錄相鄰的兩個階段的狀態(tài)即可，這就是滾動數(shù)組的原理。

Noip2023金明的預(yù)算方案22/problem.php?id=1579

金明今天很開心，家里購置的新屋就要領(lǐng)鑰匙了，新屋里有一間金明自己專用的很寬大

第13頁/共50頁

信息學(xué)競賽中的動態(tài)規(guī)劃專題

的房間。更讓他高興的是，媽媽昨天對他說：“你的房間需要購買哪些物品，怎么布置，你說了算，只要不超過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ì)一個滿足要求的購物單。

第1行為兩個正整數(shù)，用一個空格隔開：N和m，（其中N（0，表示該物品為附件，q是所屬主件的編號）

只有一個正整數(shù)，為不超過總錢數(shù)的物品的價格與重要度乘積的總和的最大值（>J)&(S^(1信息學(xué)競賽中的動態(tài)規(guī)劃專題

F[I,J]=F[I-1,J-1],其中A[I]B[J]；

計(jì)算LCS長度的時間復(fù)雜度：O（LEN_A·LEN_B），構(gòu)造LCS的時間復(fù)雜度：O（LEN_A+LEN_B）。

Ioi2000Palindrome22/problem.php?id=1866

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

第一行包含一個數(shù)字N（N≤5000），表示字符串的長度，第二行包含一個長度為N的字符串。

只有一個正整數(shù)，為將給定字符串變成回文詞所需要插入的最少字符數(shù)。

5

Ab3bd

2這個問題相當(dāng)于把將原串從某點(diǎn)截成兩段，求前一段與后一段的逆串的最長公共子序列。和合唱隊(duì)型類似，不要先枚舉分割點(diǎn)，將原串和其逆串的最長公共子序列的最長公共子序列計(jì)算之后再做分割處理。我們前面提到過LIS，現(xiàn)在又介紹了LCS，下面討論一下它們的結(jié)合體：最長公共上升子序列（LCIS）。對于LCIS的定義如下：

給出兩個長度分別為n,m的序列A和B。求出一個長度最長序列C，滿足：

C1AI且BQ>BJ。該算法的時間繁雜度為O（N4）。為了提高算法效率，我們需要去掉一些重復(fù)計(jì)算，例如上述算法中存在L使ＢL時，第i顆珠子的尾標(biāo)記應(yīng)當(dāng)?shù)扔诘趇+1顆珠子的頭標(biāo)記。第N顆珠子的尾標(biāo)記應(yīng)當(dāng)?shù)扔诘?顆珠子的頭標(biāo)記。

至于珠子的順序，你可以這樣確定：將項(xiàng)鏈放到桌面上，不要出現(xiàn)交織，隨意指定第一顆珠子，然后按順時針方向確定其他珠子的順序。

只有一個正整數(shù)E（E≤2.1*109），為一個最優(yōu)聚合順序所釋放的總能量。

4

23510

710

第21頁/共50頁

信息學(xué)競賽中的動態(tài)規(guī)劃專題

記A[I]為第I顆能量珠的首標(biāo)記，也同時是它前面那顆能量珠的尾標(biāo)記。設(shè)F[I,J]為從以A[I]為首標(biāo)記的能量珠開始順時針數(shù)到以A[J]為尾標(biāo)記的能量珠為止所有能量珠組成的串合并后放出的最大能量。則有：F[I,J]=Max{F[I,K]+F[K,J]+A[I]*A[K]*A[J]}(K=I..J)。

計(jì)算F[I,J]時，只會用到含有能量珠數(shù)目比它少的串在數(shù)組中的值，所以要依照串的能量珠數(shù)目依次增大的順序遞推。接下來，假使解決環(huán)的問題呢？枚舉分割點(diǎn)是一種方法，但是會把時間繁雜度增加到O（N4）。所以我們不如將原串復(fù)制一份加到原串的后面再進(jìn)行動態(tài)規(guī)劃。

HLJCPC2023Max/index.php?act=problem&id=1218

給出一個表達(dá)式請你添加一些括號使最終的結(jié)果盡可能的大，譬如下面的表達(dá)式：1+2*3

直接看的結(jié)果是7，然而假使添加一個括號，如(1+2)*3，那么它的結(jié)果就是9了。實(shí)際上，9也是最大的結(jié)果。

第一行是一個正整數(shù)N（2≤N≤100），其次行是一個表達(dá)式，只包含*和+兩種運(yùn)算符，N個數(shù)字間有N-1個運(yùn)算符，其中數(shù)字可以為負(fù)數(shù)。

只有一個正整數(shù)即表達(dá)式可以到達(dá)的最大值。

4

1+2*3+-1

8題目的做法基本和矩陣乘法一致，但是需要注意一點(diǎn)：由于乘法運(yùn)算的存在（兩個最小負(fù)數(shù)的乘積可能成為最大值），我們不僅要保存某部分表達(dá)式的最大值，還要保存它的最小值。設(shè)F[I,J]表示表達(dá)式從I到J部分的最大值，G[I,J]表示表達(dá)式從I到J部分的最小值，則有：Sign[i]=?*?時

F[I,J]=Max{F[I,K]*F[K+1,J],G[I,K]*F[K+1,J],F[I,K]*G[K+1,J],G[I,K]*G[K+1,J]}G[I,J]=Min{F[I,K]*F[K+1,J],G[I,K]*F[K+1,J],F[I,K]*G[K+1,J],G[I,K]*G[K+1,J]}Sign[i]=?+?時

F[I,J]=Max{F[I,K]+F[K+1,J]}G[I,J]=Min{G[I,K]+G[K+1,J]}

AsyzOI2023龍珠外掛

第22頁/共50頁

信息學(xué)競賽中的動態(tài)規(guī)劃專題

龍珠是騰訊公司新推出的一個游戲項(xiàng)目。目的是為了有效的防止外掛，終究這個游戲不是那么的簡單。龍珠的規(guī)則是這樣的：有一串n個帶顏色的球（最多可能有紅、黃、藍(lán)和綠四種顏色），你可以向這個串里加球，當(dāng)有連續(xù)三個或三個以上一致顏色的球連在一起時，我們稱為可消除狀態(tài)，通過一次加球新產(chǎn)生出的可消除狀態(tài)才真正意義上的可消除。我們?yōu)榱碎_發(fā)外掛，要找一個參與盡可能少的球并能將整串球全部消除的方案。

舉個n=12的時候的例子，整個串的消除過程如下：

第一步，在第四個球前參與一個藍(lán)色球；

其次步，在第八個球前參與一個藍(lán)色球；

第三步，在第八個球前參與一個藍(lán)色球；

第四步，在其次個球前參與一個綠色球；第五步，在其次個球前參與一個綠色球；

第六步，在第一個球前參與一個紅色球。這樣就把整個串消除了，當(dāng)然，方法不唯一。

輸入的第一行是一個整數(shù)n（1≤n≤100），表示初始的球數(shù)。其次行有一個由n個字符組成的字符串，每個字符只可能是R（紅）Y（黃）B（藍(lán)）G（綠）其中的一個。

輸出包括一個整數(shù)k，表示消除整個串最少需要放入k個球。

12

RGRRRYBYYRBB

6未解決，--!，求教ww大牛。

2.2.1其他二維狀態(tài)劃分的動態(tài)規(guī)劃舉例

CentralEuropean2000I-KeyBoard/hoj/problem/view?id=1042

移動電話用戶都對使用電話鍵盤輸入英文短消息感到煩透了。有時你真的沒有心情輸入

第23頁/共50頁

信息學(xué)競賽中的動態(tài)規(guī)劃專題

長一點(diǎn)兒的信息，由于尋常要按一個數(shù)字鍵好幾下才能輸入一個字母！這都?xì)w咎于數(shù)字鍵太少——典型的電話鍵盤只有12個鍵，更糟的是只有其中8個可以用來輸入26個英文字母，它的設(shè)計(jì)如下面的圖所示。

每個鍵可以對應(yīng)一組字母。假使你想輸入某一組的第1個字母，你按一下對應(yīng)的鍵就行了；假使你要第2個，那你得按兩下；假使是第3個或者第4個??這種鍵盤的設(shè)計(jì)者并不在乎你按鍵次數(shù)的多少，他們只看重平均分派字母。有些字母的使用頻率要高些，但它們被安排在一組字母的第3個或第4個。例如S是個常用的字母，但我們要按4下才能輸入一個S。

而我們需要你編寫一個程序，找到一種最優(yōu)的鍵盤（對于給定的字母使用頻率）。當(dāng)然，不管如何安排字母和按鍵的對應(yīng)關(guān)系都必需保持字母的順序，這樣用戶才不會感到頭暈。不過你可以安排任意數(shù)量的字母對應(yīng)一個按鍵。

輸入第一行有兩個整數(shù)K和L（1≤K≤L）。K表示提供按鍵的個數(shù)，L表示有多少字符需要安排到鍵盤上。接下來L行，每行是一個非負(fù)整數(shù)，這些數(shù)字依次表示字母表中字符的使用頻率。較大的數(shù)字表示較高的使用頻率。這些數(shù)字最大不超過10000。

輸出包括一個整數(shù)S。S為所有字符的輸入代價和的最小可能值，一個字符的輸入代價定義為其使用頻率與輸入這個字母需要的按鍵次數(shù)的乘積。一定要注意：所有字母在鍵盤上的排列順序是不能改變的。

82633715891575161462129717731904

第24頁/共50頁

信息學(xué)競賽中的動態(tài)規(guī)劃專題

29891232091588151329963269108012127263083436813345189999427733871

87180

顯然地，設(shè)F[I,J]表示前I個鍵盤存有前J個字母的最小代價和，則有：F[I,J]=Min{F[I-1,K]+G[K+1,J]}，其中G[K+1,J]表示把第K+1個字母到第J個字母存在一個鍵上的最小代價和。數(shù)組G需要遞推，總體算法的時間繁雜度為O（N3）。

USACOJan2023ProblemSolving22/problem.php?id=1867

這些日子，F(xiàn)J的奶牛一共有P(1≤P≤300)個待解決的問題。奶?，F(xiàn)在是上班族了，每個月的工資為M(1≤M≤1000)。

奶?，F(xiàn)在需要雇人來解決那些問題，其中有一個專家十分可靠，可以每一個月解決一個問題。他的收費(fèi)方式是這樣子的：解決問題前后各付一次錢(1≤payment≤M)，當(dāng)然奶牛必需在當(dāng)時能夠支付足夠的錢。求解決這些問題所需要的最小時間。還有一點(diǎn)：這些問題是有嚴(yán)格先后順序的。

第一行是兩個正整數(shù)M和P，以下P行每行兩個數(shù)，表示解決該問題前后分別需要付的費(fèi)用。

只有一個正整數(shù)即解決全部問題需要的最小月份數(shù)。

第25頁/共50頁

信息學(xué)競賽中的動態(tài)規(guī)劃專題

100540206020305030504040

6

+++++++||Avail|Probs|Before|After|Candy||Month|Money|Solved|Payment|Payment|Money|+++++++|1|0|-none-|0|0|0||2|100|1,2|40+60|0|0||3|100|3,4|30+30|20+20|0||4|100|-none-|0|50+50|0||5|100|5|40|0|60||6|100|-none-|0|40|60|+++++++

設(shè)F[X,Y]表示解決前X個問題且最終一個月解決了Y個問題所需要的最小月份數(shù)。利用輔助數(shù)組G1[X,Y]和G2[X,Y]表示在一個月解決問題X到問題Y間所有問題前后需要支付的費(fèi)用。則有狀態(tài)轉(zhuǎn)移方程：F[I,J]=Min{F[K][I-1]+P[I,J,K]}，其中G1[I,J]+G2[K,I-1]不超過M時，P[I,J,K]=1，否則P[I,J,K]=2。這種算法的時間繁雜度為O（N3）。

和LIS一樣，可以參與貪心思想，假使設(shè)F[X]表示解決前X個問題需要的最小月份數(shù)，同時用輔助數(shù)組G[X]表示解決前X個問題取得最小月份時，該月最少花費(fèi)的錢數(shù)。則有狀態(tài)轉(zhuǎn)移方程：F[I]=Min{F[J]+Q[J,I,G[X]]}，并隨時更新G[X]，則把時間繁雜度降到了O（N2）。

2.3樹型狀態(tài)劃分的動態(tài)規(guī)劃

顧名思義，樹型狀態(tài)劃分的動態(tài)規(guī)劃就是在“樹〞的數(shù)據(jù)結(jié)構(gòu)上的動態(tài)規(guī)劃。由樹的結(jié)構(gòu)可知，樹型動態(tài)規(guī)劃的方向一般是葉到根：將根的子節(jié)點(diǎn)傳遞有用的信息給根，使根得出最優(yōu)解。

URAL1039Anniversary22/problem.php?id=1849

有個公司要舉行一場晚會。

為了能玩得開心，公司領(lǐng)導(dǎo)決定：假使邀請了某個人，那么一定不會邀請他的上司

第26頁/共50頁

信息學(xué)競賽中的動態(tài)規(guī)劃專題

（上司的上司，上司的上司的上司??都可以邀請）。

每個參與晚會的人都能為晚會增加一些氣氛，求一個邀請方案，使氣氛值的和最大。

第1行一個整數(shù)N（1≤N≤6000）表示公司的人數(shù)。

接下來N行每行一個整數(shù)。第i行的數(shù)表示第i個人的氣氛值x(-128≤x≤127)。接下來每行兩個整數(shù)L，K。表示第K個人是第L個人的上司。輸入以00終止。

只有一個數(shù)，最大的氣氛值和。

7111111113236474453500

5設(shè)F[I]表示邀請I的最大值，G[I]表示不邀請I的最大值。則F[I]=∑{G[I.sons]},G[I]=∑{Max(F[I.sons],G[I.sons]}}。大多的樹型動態(tài)規(guī)劃可以化成類似的類型，下面介紹一下多叉樹改造為二叉樹的方法。

Ctsc1997選課22/problem.php?id=1290

在大學(xué)里每個學(xué)生，為了達(dá)到一定的學(xué)分，必需從好多課程里選擇一些課程來學(xué)習(xí)，在課程里有些課程必需在某些課程之前學(xué)習(xí)，如高等數(shù)學(xué)總是在其它課程之前學(xué)習(xí)?，F(xiàn)在有N門功課，每門課有個學(xué)分，每門課有一門或沒有直接先修課（若課程a是課程b的先修課即只有學(xué)完了課程a，才能學(xué)習(xí)課程b）。一個學(xué)生要從這些課程里選擇M門課程學(xué)習(xí)，問他能獲得的最大學(xué)分是多少？

第27頁/共50頁

信息學(xué)競賽中的動態(tài)規(guī)劃專題

第一行有兩個整數(shù)N,M用空格隔開。(1≤N≤200,1≤M≤150)

接下來的N行,第I+1行包含兩個整數(shù)ki和si,ki表示第I門課的直接先修課，si表示第I門課的學(xué)分。若ki=0表示沒有直接先修課（1≤ki≤N,1≤si≤20）。

只有一行，選M門課程的最大得分。

7422010421717622

13

以樣例數(shù)據(jù)為例，很簡單建出一棵樹（如右圖所示）。我們可以選取某一個點(diǎn)K的條件只是它的父節(jié)點(diǎn)已經(jīng)被選取或者它自己為根節(jié)點(diǎn)；而且我們不管如何取K的子

孫節(jié)點(diǎn)，都不會影響到它父節(jié)點(diǎn)的選取狀況，這滿足無后效性原則。我們用函數(shù)F[I,J]表示以第I個節(jié)點(diǎn)為父節(jié)點(diǎn)，取J個子節(jié)點(diǎn)的最正確代價，則可以進(jìn)行動態(tài)規(guī)劃?？墒侨绱艘?guī)劃，其效率與探尋毫無區(qū)別。

我們不妨改造樹，將其轉(zhuǎn)變?yōu)槎鏄?。變化方法為：一個節(jié)點(diǎn)的第一個孩子為其左孩子，而一個節(jié)點(diǎn)的兄弟為其右孩子。以樣例數(shù)據(jù)為例，建出一棵二叉樹（如右圖所示）。轉(zhuǎn)化的時間繁雜度為O（N）。我們還是利用同樣的狀態(tài)表示方法，則有狀態(tài)轉(zhuǎn)移方程：

F[I,J]=Max（F[L,K]+F[R,J-K-1]+S[I],F[R,J]）整個算法的時間繁雜度為O（N3）。在實(shí)現(xiàn)樹型動態(tài)規(guī)劃的時候，尋常使用后序遍歷。

第28頁/共50頁

信息學(xué)競賽中的動態(tài)規(guī)劃專題

3.動態(tài)規(guī)劃的輔助與優(yōu)化方法

3.1.1填鴨這里說的填鴨尋常也被視為動態(tài)規(guī)劃，我們先來看一個經(jīng)典的硬幣問題：給出N種硬幣的面值，問面值M有多少種不同的表示方法。我們常見的解法就是設(shè)F[I]表示面值為I的不同表示方法，則F[I]=∑F[I-Cost[J]]。這種填鴨沒有決策，就是開一個大的數(shù)組，把代價值一個一個地填進(jìn)去。再舉一個簡單的游戲——步步為零。游戲者在一張菱形的表格中依照規(guī)則跳動，使得跳到的數(shù)字經(jīng)過加號和減號的連接，盡可能的迫近零。游戲者從最下面的方格出發(fā)，依照每次可以往上面左右兩個格子的任意一格跳動，當(dāng)游戲者跳到最頂端的方格時，游戲終止。在游戲未終止前，游戲者不允許跳到表特別。

231-357610-220-7-5–81087

對于上面的表格，最好的跳動方案是：7+8+(-5)+(-2)-5-1-2=0或7+10+(-7)-6+(-3)-3+2=0或7+10+(-5)-10-5+1+2=0或7+10+(-5)+(-2)-5-3-2=0。

利用填鴨的方法，設(shè)F[I,J,K]表示到第I層第J個數(shù)字組成K的可能性，則有F[I,J,K]=F[I+1,J-1,K+A[I,J]]orF[I+1,J-1,K-A[I,J]]orF[I+1,J,K+A[I,J]]orF[I+1,J,K-A[I,J]]。

Oibh2023胖子三角

最近，地球上興起了一股“登月熱〞。人們紛紛報名參與太空游。胖子這個摩登青年當(dāng)然不會落伍?，F(xiàn)在，胖子乘神州X號來到月球，準(zhǔn)備開拓一片新的天地。他在月球上建立了一個食堂，并且想給他的月球食堂建造一個圍欄。路人皆知的是胖子很愛吃，而且胖子很虛榮，為了使圍欄看起來很酷，而且很像麥當(dāng)勞的珍寶三角，胖子決定用面包把它建成三角形。胖子現(xiàn)在擁有N(3信息學(xué)競賽中的動態(tài)規(guī)劃專題

3435

6

每一個面包可以被包含在三條邊中的任意一條邊中，設(shè)F[I,J,K]表示用前I個面包組成一條長度為J的邊和一條長度為K的邊的可能性，則有狀態(tài)轉(zhuǎn)移方程：F[I,J,K]=F[I-1,J-AI,K]orF[I-1,J,K-AI]。最終枚舉一下組成的可能所有三角型，取其中面積最大的?？偟臅r間繁雜度為O（N3L2）。

NEYCoi2023搭建雙塔

2023年9月11日，一場突發(fā)的災(zāi)難將紐約世界貿(mào)易中心大廈夷為平地，Mr.F曾親眼目睹了這次災(zāi)難。為了紀(jì)念“9.11〞事件，Mr.F決定自己用水晶來搭建一座雙塔。Mr.F有N塊水晶，每塊水晶有一個高度，他想用這N塊水晶搭建兩座有同樣高度的塔，使他們成為一座雙塔，Mr.F可以從這N塊水晶中任取M（1≤M≤N）塊來搭建。但是他不知道能否使兩座塔有同樣的高度，也不知道假使能搭建成一座雙塔，這座雙塔的最大高度是多少。所以他來請你幫忙。

給定水晶的數(shù)量N（1≤N≤100）和每塊水晶的高度Hi（N塊水晶高度的總和不超過2000），你的任務(wù)是判斷Mr.F能否用這些水晶搭建成一座雙塔（兩座塔有同樣的高度），假使能，則輸出所能搭建的雙塔的最大高度，否則輸出“Impossible〞。

輸入的第一行為一個數(shù)N，表示水晶的數(shù)量。其次行為N個數(shù)，第i個數(shù)表示第i個水晶的高度。

輸出僅包含一行，假使能搭成一座雙塔，則輸出雙塔的最大高度，否則輸出一個字符串“Impossible〞。

5

12435

7最基本的方法還是填鴨，設(shè)F[I,J,K]表示用前I個水晶組成一塔高度為J另一塔高度為K的可能性，則有狀態(tài)轉(zhuǎn)移方程：F[I,J,K]=F[I-1,J-AI,K]orF[I-1,J,K-AI]orF[I-1,J,K]。時間繁雜度為O（N3H2）。

第30頁/共50頁

信息學(xué)競賽中的動態(tài)規(guī)劃專題

實(shí)際上，假使設(shè)F[I,J]表示用前I個水晶組成一對高度差為J的較低塔的最高高度，就可以把時間繁雜度降為O（N2）。

3.1.2排序排序是一件利器，經(jīng)常被使用在參與貪心思想的動態(tài)規(guī)劃問題當(dāng)中，通過也會出現(xiàn)在避免出現(xiàn)重復(fù)的問題當(dāng)中，貪心思想的例子前面說過了好多，下面將舉例說明排序在動態(tài)規(guī)劃問題中的應(yīng)用。

GYoi2023購物計(jì)劃

寧寧利用假期打工賺了一大筆錢，這使得她十分想上街進(jìn)行一次大購買。寧寧有個壞習(xí)慣，看到東西就想買。

阿月為此傷透了腦筋，最終他決定為寧寧來計(jì)劃先買哪些東西后買哪些東西，以此來為寧寧省錢。寧寧也很心疼自己的錢，于是決定依照阿月的計(jì)劃來安排買東西的先后順序，但是有一點(diǎn)可以確定：只要她口袋里的錢數(shù)不低于m元就要繼續(xù)買東西。

阿月需要你的幫助，他希望寧寧最終剩下的錢越多越好。

輸入第一行包括三個正整數(shù)n，m和s（n≤100，0≤m,s≤10000），表示街上出售的商品共有n種，而寧寧口袋里最初有s元錢。其次行包含n個用空格分隔的不超過1000的正整數(shù)，表示對應(yīng)商品的價格。

輸出只包含一個非負(fù)整數(shù)t，即寧寧最終能剩下的最大錢數(shù)。

45102742

4

阿月要求寧寧先買商品1和商品3之后，寧寧只剩下4元錢，低于m=5元，于是中止購物，最終剩下4元。寧寧中止購物有兩種狀況：錢數(shù)低于m元或者沒有東西可買。第一種狀況用填鴨的方法可以輕松解決。而其次種狀況則需要提前判斷，如何判斷買過一些東西之后什么都買不起了呢？為了保證買不起A[I]時，A[I+1..N]也都買不起，需要把商品的價值從小到大排序，從小的開始買，累和為t，滿足s-t第31頁/共50頁

信息學(xué)競賽中的動態(tài)規(guī)劃專題

GreaterNewYork2023MargaritasontheRiverWalk/problem?id=3093

有幾種不同價格的瑪格麗塔酒，給你一定的錢，讓你去買酒。規(guī)定每種酒只能買一瓶，而且要買到你沒有足夠的錢去買其它的酒為止。

問總共有多少種不同的購買方案。例如，你有25元錢，有六種酒，價格如下VendorABCDHJPrice8987165

可能的購買方案有ABC(25),ABD(24),ABJ(22),ACD(23),ACJ(21),ADJ(20),AH(24),BCD(24),BCJ(22),BDJ(21),BH(25),CDJ(20),CH(24),DH(23)HJ(21)共15種方案。

第一行包括兩個正整數(shù)N和V，表示酒的種類和持有的錢數(shù)，接下來一行包含N個正整數(shù)表示每種酒的價格。

方案總數(shù)。

625

8987165

15

題目要求剩下的錢數(shù)要小于任何未選擇的酒的價格，即小于未被選擇的最小價格。因此，我們需要對所有酒按價格由小到大排序，再作探討。

假設(shè)未被選擇的最小價格的酒是第I個，那么首先可以確定前I-1個酒一定是被選擇的，亦可以確定第I+1個到第N個酒的所有可行組合的價格和S滿足V-V[I]信息學(xué)競賽中的動態(tài)規(guī)劃專題

狀態(tài)的規(guī)模與狀態(tài)表示的方法密切相關(guān)，通過改進(jìn)狀態(tài)表示減小狀態(tài)總數(shù)是應(yīng)用較為普遍的一種方法。

USACO5.6.2RaucousRockers22/problem.php?id=1460

現(xiàn)有n首由RaucousRockers演唱組錄制的寶貴的歌曲，計(jì)劃從中選擇一些歌曲來發(fā)行m張唱片，每張唱片至多包含t分鐘的音樂，唱片中的歌曲不能重疊。按下面的標(biāo)準(zhǔn)進(jìn)行選擇：

（1）這組唱片中的歌曲必需依照它們創(chuàng)作的順序排序；（2）包含歌曲的總數(shù)盡可能多。

n，m，t，（1≤n,m,t≤20）和n首歌曲的長度，它們依照創(chuàng)作順序排序，沒有一首歌超出一張唱片的長度，而且不可能將所有歌曲的放在唱片中。

輸出所能包含的最多的歌曲數(shù)目。

4524342

3

設(shè)N首歌曲依照寫作順序排序后的長度為L[1..N]，F(xiàn)[I,J,K]表示前I首歌曲，用J張唱片另加K分鐘來錄制，最多可以錄制的歌曲數(shù)目，則有：

K≥L[I]時

F[I,J,K]=Max{F[I-1,J,K-L[I]],F[I-1,J,K]}K3時

M[I,J]=M[I,J]orM[I+1,J-I*K]

這樣，若存在K，使得M[3,K]=true且M[4,Mid-K]=true，則可以實(shí)現(xiàn)題目要求，否則無法實(shí)現(xiàn)。

第36頁/共50頁

信息學(xué)競賽中的動態(tài)規(guī)劃專題

上圖基本反映了此題優(yōu)化的效果?？梢缘贸鼋Y(jié)論：雙向擴(kuò)展以減少狀態(tài)量的方法不僅適用于狀態(tài)空間探尋，同樣適用于動態(tài)規(guī)劃。

3.2.3減少每次狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)這里介紹一下四邊形不等式及其應(yīng)用，引例就用經(jīng)典的石子合并問題。

Noi1995石子合并問題22/problem.php?id=1868

在一個操場上擺放著一排n（n≤20）堆石子。現(xiàn)要將石子有次序地合并成一堆。規(guī)定每次只能選相鄰的2堆石子合并成新的一堆，并將新的一堆石子數(shù)記為該次合并的得分。試編程求出將n堆石子合并成一堆的最小得分和最大得分以及相應(yīng)的合并方案。

這是一個典型的二維狀態(tài)劃分的動態(tài)規(guī)劃，設(shè)F[I,J]表示合并D[I..J]所得到的最小得分（最大得分同理），W[I,J]表示D[I..J]區(qū)間的石子的總得分，則有F[I,J]=Min{F[I,K-1]+F[K,J]}+W[I,J]。

當(dāng)函數(shù)G[I,J]滿足G[I,J]+G[I?,J?]≤G[I?,J]+G[I,J?]且I≤I?≤J≤J?時，稱G滿足四邊形不等式。在石子合并問題中，W顯然滿足四邊形不等式。當(dāng)函數(shù)G[I,J]滿足G[I?,J]≤G[I,J?]且I≤I?≤J≤J?時稱G關(guān)于區(qū)間包含關(guān)系單調(diào)，簡稱單調(diào)。那么在石子合并問題中，W也顯然單調(diào)。由遞推關(guān)系和數(shù)學(xué)歸納法可知，F(xiàn)也滿足四邊形不等式。

令S[I,J]=Max{K|F[I,J]=F[I,K-1]+F[K,J]+W[I,J]}，即令F[I,J]取得最小值的K的最大值?？梢宰C明S單調(diào)，即I≤I?≤J≤J?時，S[I?,J]≤S[I,J?]。

由于證明過于繁雜，這里只證明要用的結(jié)論，即I≤J且I?=I,J?=J+1時，S[I,J]≤S[I,J+1]。由于F滿足四邊形不等式，則有：K≤K?≤J≤J+1時，F(xiàn)[K,J]+F[K?,J+1]≤F[K?,J]+F[K,J+1]，設(shè)FK[I,J]=F[I,K-1]+F[K,J]+W[I,J]，不等式左右兩邊添加4項(xiàng)有：

(F[I,K-1]+F[K,J]+W[I,J])+(F[I,K?-1]+F[K?,J+1]+W[I,J+1])

≤

(F[I,K-1]+F[K,J+1]+W[I,J+1])+