2.7　動態(tài)規(guī)劃初步

本節(jié)選解習(xí)題來源于《算法競賽入門經(jīng)典（第2版）》一書的第9章。

習(xí)題9-1　最長的滑雪路徑（Longest Run on a Snowboard，UVa 10285）

在一個(gè)R*C（R，C≤100）的整數(shù)矩陣上找一條高度嚴(yán)格遞減的最長路。起點(diǎn)任意，但每次只能沿著上下左右4個(gè)方向之一走一格，并且不能走出矩陣外。如圖2.51所示，最長路就是按照高度25、24、23、…、2、1這樣走，長度為25。矩陣中的數(shù)均為0～100。

【分析】

用D［i，j］來表示從［i，j］開始能走的高度嚴(yán)格遞減的最長路，則很容易發(fā)現(xiàn)D［i，j］的狀態(tài)轉(zhuǎn)移方程：D［i，j］＝max（1＋D［i1，j1］），其中（i1，j1）是比［i，j］高度小的4個(gè)相鄰的格子之一。邊界條件是當(dāng)沒有符合條件的i1和j1時(shí)，D［i，j］＝1。使用記憶化搜索即可，時(shí)間復(fù)雜度是O（R*C）。

習(xí)題9-2　免費(fèi)糖果（Free Candies，UVa10118）

桌上有4堆糖果，每堆有N（N≤40）顆。佳佳有一個(gè)最多可以裝5顆糖的小籃子。他每次選擇一堆糖果，把最頂上的一顆拿到籃子里。如果籃子里有兩顆顏色相同的糖果，佳佳就把它們從籃子里拿出來放到自己的口袋里。如果籃子滿了而里面又沒有相同顏色的糖果，游戲結(jié)束，口袋里的糖果就歸他了。當(dāng)然，如果佳佳足夠聰明，他有可能把堆里的所有糖果都拿走。為了拿到盡量多的糖果，佳佳該怎么做呢？

【分析】

初步看，狀態(tài)包含4堆糖果的高度hs［4］以及當(dāng)前籃子內(nèi)是否有各色糖果。如果全部考慮進(jìn)去，空間復(fù)雜度會大到無法接受。思考之后會發(fā)現(xiàn)，只要有兩個(gè)相同的糖果就會被拿出來，對于特定的hs，籃子中的狀態(tài)就可以確定。

可以對hs［4］進(jìn)行回溯搜索，每一步嘗試從一堆糖果頂端取出一個(gè)糖果。同時(shí)記憶hs對應(yīng)的狀態(tài)，減少重復(fù)計(jì)算。算法的時(shí)間和空間復(fù)雜度都剛好是O（n⁴）。完整程序如下：

習(xí)題9-3　切蛋糕（Cake Slicing，ACM/ICPC Nanjing 2007，UVa1629）

有一個(gè)n行m列（1≤n，m≤20）的網(wǎng)格蛋糕上有一些櫻桃。每次可以用一刀沿著網(wǎng)格線把蛋糕切成兩塊，并且只能夠直切不能拐彎。要求最后每一塊蛋糕上恰好有一個(gè)櫻桃，且切割線總長度最小。如圖2.52所示是一種切割方法。

【分析】

有一個(gè)明顯的遞歸子結(jié)構(gòu)，就是包含1個(gè)以上櫻桃的子矩形r、c、w、h。左上角[r,c]，寬為w、高為h。

記D(r,c,w,h)（下文簡稱d）為這個(gè)矩形的最小切割線長度，對于這個(gè)矩形來說，只有橫豎兩種切法：

（1）遍歷所有合法的橫切，d=min(d, min(w+D(r+i, c, w, h-i)+D (r, c, w, i))), i∈[1,h]。

（2）遍歷所有合法的豎切，d=min(d, min(h+D(r,c,i,h)+D (r, c+i, w-i, h))), i∈ [1,w]。

邊界條件是(r,c,w,h)對應(yīng)的子矩形中剛好只有1個(gè)櫻桃，此時(shí)d=0。遍歷時(shí)需要保證切開的兩個(gè)矩形都至少包含1個(gè)櫻桃。

在遍歷過程中需要求出每個(gè)子矩形的櫻桃個(gè)數(shù)，可以用求D類似的遞歸結(jié)構(gòu)來記憶化搜索所有子矩形的櫻桃個(gè)數(shù)。算法的時(shí)空復(fù)雜度都是O(n³m³)。完整程序（C++11）如下：

習(xí)題9-4　串折疊（Folding, ACM/ICPC NEERC 2001, UVa1630）

給一個(gè)由大寫字母組成的長度為n（1≤n≤100）的串，“折疊”成一個(gè)盡量短的串。例如AAAAAAAAAABABABCCD折疊成9（A）3（AB）CCD。折疊是可以嵌套的，例如NEERCYESYESYESNEERCYESYESYES可以折疊成2（NEERC3（YES））。多解時(shí)可以輸出任意解。

【分析】

參考“最優(yōu)矩陣鏈乘”問題的思路，進(jìn)行區(qū)間規(guī)劃。記輸入串為S，DP（L，R）表示這個(gè)區(qū)間的最優(yōu)折疊結(jié)果的字符串表示，用STL的string來存儲。則狀態(tài)轉(zhuǎn)移方程如下：

（1）邊界條件：L＝R時(shí)，DP（L，R）＝“S［L］“。

（2）L＜R，則考慮兩種策略，取長度最短的方案：

• □　把區(qū)間切分成兩部分，分別折疊然后拼接，遍歷所有的區(qū)間切分方案［L，k］和［k＋1，R］（L≤k＜R），求出令DP（L，k）和DP（k＋1，R）長度之和最小的k值kMin，則有DP（L，R）＝DP（L，kMin）＋DP（kMin＋1，R）。
• □　如果S［L，R］是周期串，首先求出最小的重復(fù)串長度cycle（0＜cycle≤（L-R＋1）／2），記rep＝（L-R＋1）／cycle，也就是重復(fù)次數(shù)。這樣把區(qū)間變成DP（L，L＋cycle-1）的rep次折疊。DP（L，R）＝“cnt（“＋“DP［L］［L＋cycle-1］“＋“）“。例如，“ABABABAB”變成“4（AB）”。

所求結(jié)果就是DP（0，n-1），算法的時(shí)間空間復(fù)雜度均為O（n³）。完整程序如下：

習(xí)題9-5　郵票和信封（Stamps and Envelope Size, ACM/ICPC World Finals 1995, UVa242）

假定一張信封最多貼5張郵票，如果只能貼1分和3分的郵票，可以組成面值1～13以及15，但不能組成面值14。我們說：對于郵票組合{1,3}以及數(shù)量上限S=5，最大連續(xù)郵資為13。1～13和15的組成方法如表2.1所示。

輸入S（S≤10）和若干郵票組合（郵票面值不超過100），選出最大連續(xù)郵資最大的一個(gè)組合。如果有多個(gè)并列，郵票組合中郵票的張數(shù)應(yīng)最多。如果還有并列，郵票從大到小排序后字典序應(yīng)最小。

【分析】

對于郵票組合C，令DP[i]表示郵資i至少需要多少張來自于C的郵票才能組合起來。則DP[i]=min(DP[i-x]+1, x∈C且x≤i)。則對于C來說最大連續(xù)郵資就是第一個(gè)符合DP[i+1]>S的i。這樣就可以求出每個(gè)組合的最大連續(xù)郵資。時(shí)間和空間復(fù)雜度都為O(100*maxS)。完整程序（C++11）如下：

習(xí)題9-6　電子人的基因（Cyborg Genes, UVa10723）

輸入兩個(gè)A～Z組成的字符串（長度均不超過30），找一個(gè)最短的串，使得輸入的兩個(gè)串均是它的子序列（不一定連續(xù)出現(xiàn)）。你的程序還應(yīng)統(tǒng)計(jì)長度最短的串的個(gè)數(shù)。如ABAAXGF和AABXFGA的最優(yōu)解之一為AABAAXGFGA，一共有9個(gè)解。

【分析】

參考LCS問題的思路。記輸入的兩個(gè)字符串為S1和S2，定義pa(i,j)為S1[1…i]和S2[1…j]的公共父串的最短長度。則pa的狀態(tài)轉(zhuǎn)移方程如下：

（1）pa(i,j)=min(pa(i-1,j)+1,pa(i,j-1)+1)，其中S1[i]≠S2[j]，對應(yīng)父串的最后一位是使用S1[i]還是S2[j]。

（2）pa(i,j)=pa(i-1,j-1)+1，其中S1[i]=S2[j]，則父串的最后一位是確定的。

（3）邊界條件是：當(dāng)i=0或者j=0時(shí)，pa(i,j)=max(i,j)，則父串一定是S1[1…i]和S2[1…j]其中之一。

然后求最短父串的方案個(gè)數(shù)：定義pac(i,j)為S1[1…i] and S2[1…j]的最短公共父串的個(gè)數(shù)。S1[i]=S2[j]時(shí)，pac(i,j)=pac(i-1,j-1)，因?yàn)楦复淖詈笠晃恢挥?種選擇。否則記p1=pa(i-1, j)，p2=pa(i, j-1) ，則有：

• □　pac(i,j)=pac(i-1, j)+pac(i, j-1)，此時(shí)p1=p2，表示父串最后一位可以使用S1[i]和S2[j]兩種方案。
• □　pac(i,j)=pac(i-1, j), p1 < p2，父串必須使用S1[i]才能保證最短。
• □　pac(i,j)=pac(i, j-1), p1 > p2，父串必須使用S2[j]才能保證最短。
• □　邊界條件是：當(dāng)i=0或者j=0時(shí)，pac(i, j)=1，父串只有1種選擇。

時(shí)間復(fù)雜度和空間復(fù)雜度都為O(|S1|*|S2|)。注意，輸入的S1和S2長度可能是0，輸入時(shí)要用gets或者STL里面的getline而不能用scanf。完整程序如下：

習(xí)題9-8　阿里巴巴（Alibaba, ACM/ICPC SEERC 2004, UVa1632）

直線上有n（n≤10000）個(gè)點(diǎn)，其中第i個(gè)點(diǎn)的坐標(biāo)是x_i，且它會在d_i秒之后消失。Alibaba可以從任意位置出發(fā)，求訪問完所有點(diǎn)的最短時(shí)間。無解輸出No solution。

【分析】

最優(yōu)的訪問策略是在任意時(shí)刻，訪問過的點(diǎn)要形成一個(gè)連續(xù)區(qū)間，中間不存在未訪問過的點(diǎn)（順路都可以把那個(gè)點(diǎn)訪問了）。

定義：

• □　D（i，j，0）：訪問i到j，最后停在i點(diǎn)所需要的最少時(shí)間。
• □　D（i，j，1）：訪問i到j，最后停在j點(diǎn)所需要的最少時(shí)間。

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

• □　D（i，j，0）＝min（D（i＋1，j，0）＋x_i＋1-x_i，D（i＋1，j，1）＋x_j-x_i），其中有兩種策略：先訪問i＋1到j，停在i＋1再去i，或者停在j再去i。
• □　D（i，j，1）＝min（D（i，j-1，1）＋x_j-x_j-1，D（i，j-1，0）＋x_j-x_i），其中有兩種策略：先拿i到j-1的物品，停在j-1再去拿j，或者停在i再去拿j。

時(shí)間和空間復(fù)雜度都為O（2*n²）。需要注意的是，題目沒有明確說，但是可以假設(shè)Alibaba單位時(shí)間移動一個(gè)單位的距離。

習(xí)題9-9　倉庫守衛(wèi)（Storage Keepers，UVa10163）

你有n（n≤100）個(gè)相同的倉庫。有m（m≤30）個(gè)人應(yīng)聘守衛(wèi)，第i個(gè)應(yīng)聘者的能力值為P_i（1≤P_i≤1000）。每個(gè)倉庫只能有一個(gè)守衛(wèi)，但一個(gè)守衛(wèi)可以看守多個(gè)倉庫。如果應(yīng)聘者i看守k個(gè)倉庫，則每個(gè)倉庫的安全系數(shù)為P_i/K的整數(shù)部分。沒人看守的倉庫安全系數(shù)為0。

你的任務(wù)是招聘一些守衛(wèi)，使得所有倉庫的最小安全系數(shù)最大，在此前提下守衛(wèi)的能力值總和（這個(gè)值等于你所需支付的工資總和）應(yīng)最小。

【分析】

類似于背包問題，令F（i，j）表示前i個(gè)人，管理j個(gè)倉庫的最小安全系數(shù)最大值，則有：

• □　F（i，0）＝INF，0個(gè)倉庫最小安全系數(shù)可以認(rèn)為是INF，方便遞推。
• □　F（1，j）＝P₁/j，每個(gè)倉庫的安全系數(shù)都是P₁/j。
• □　記k為第i個(gè)人管理的倉庫個(gè)數(shù)（0≤k≤j），G（k）為第i個(gè)人管理k個(gè)倉庫時(shí)，前j個(gè)倉庫最小安全系數(shù)的最大值。則k＝0時(shí)，G（0）＝F（i-1，j），否則G（k）＝min（F（i-1，j-k），P_i/k)。F(i,j)=max(G(k))。

記mx＝F（m，n），然后就是求工資總和：G（i，j）表示前i個(gè)人，管理j個(gè)倉庫的達(dá)到最大安全系數(shù)前提下，這i個(gè)人能力總和的最小值。

• □　G（i，0）＝0，0個(gè)倉庫只需要0個(gè)人管。
• □　G（1，j）＝P_i/j≥mx？P_i：INF，只能選擇讓安全系數(shù)超過最大值的人來管理這G個(gè)倉庫。
• □　G（i，j）＝min（G（i-1，j-k）＋P_i），其中P_i/k≥mx & 0≤k≤j，這里依然是對第i個(gè)人管理的倉庫個(gè)數(shù)k進(jìn)行決策。

需要注意的是，上述狀態(tài)轉(zhuǎn)移過程中，如果k＝0，則有P_i/k＝INF。空間復(fù)雜度為O（n*m），時(shí)間復(fù)雜度為O（n²*m）。完整程序（C＋＋11）如下：

習(xí)題9-10　照亮體育館（Barisal Stadium, UVa10641）

輸入一個(gè)凸n（3≤n≤30）邊形體育館和多邊形外的m（1≤m≤1000）個(gè)點(diǎn)光源，每個(gè)點(diǎn)光源都有一個(gè)費(fèi)用值。選擇一組點(diǎn)光源，照亮整個(gè)多邊形，使得費(fèi)用值總和盡量小。如圖2.53所示，多邊形ABCDEF可以被兩組光源{1,2,3}和{4,5,6}照亮。光源的費(fèi)用決定了哪組解更優(yōu)。

【分析】

照亮整個(gè)多邊形，也就是要選擇一組費(fèi)用最小的光源，使得每個(gè)頂點(diǎn)都被照亮。首先需要計(jì)算出每個(gè)光源可以照到哪些頂點(diǎn)。例如，圖2.53中光源1可以照亮邊AB（包含A、B兩個(gè)頂點(diǎn)），一定存在多邊形內(nèi)部的一個(gè)點(diǎn)，剛好和點(diǎn)1分別位于AB的不同側(cè)。進(jìn)一步，先通過把所有頂點(diǎn)坐標(biāo)求平均值得到一個(gè)多邊形內(nèi)部的點(diǎn)O，再使用叉積來計(jì)算每個(gè)光源可以照亮的邊和頂點(diǎn)。

而本題中所有頂點(diǎn)形成一個(gè)環(huán)，不難想到首先要把環(huán)變成直線，可以把區(qū)間[0,n)擴(kuò)大兩倍成為[0,2n)，其中i≥n對應(yīng)原來的點(diǎn)i-n，然后再預(yù)處理出每個(gè)光源能夠照亮的頂點(diǎn)編號區(qū)間[L,R]。一組光源只要能把[0,2n)的任意一個(gè)包含n個(gè)頂點(diǎn)的子區(qū)間內(nèi)的所有頂點(diǎn)都照亮，就是一組符合要求的解?，F(xiàn)在就是要求出所有解中費(fèi)用最小的。

對于頂點(diǎn)i（0≤i<n）：定義D(j)為頂點(diǎn)編號區(qū)間[i, j)內(nèi)的頂點(diǎn)都被照射到所需的最小費(fèi)用，則本題的解就是min(D(i+n)), 0≤i<n。對于每個(gè)i，從小到大遍歷頂點(diǎn)編號j（i≤j<i+n），然后考慮每個(gè)能照射到j的光源lt，記r=min(lt.R,i+n)，表示使用了lt之后，能夠照射到的右邊界。分是否使用lt兩種情況考慮進(jìn)行狀態(tài)轉(zhuǎn)移，用D(j)更新D(r)：D(r)=min(D(r),D(j)+lt.c)，其中l(wèi)t.c表示光源lt的費(fèi)用。

時(shí)間復(fù)雜度為O(2n²m)，空間復(fù)雜度為O(n)。完整程序如下：

習(xí)題9-11　禁止的回文子串（Dyslexic Gollum, ACM/ICPC Amritapuri 2012, UVa1633）

輸入正整數(shù)n和k（1≤n≤400，1≤k≤10），求長度為n的01串中有多少個(gè)不含長度至少為k的回文連續(xù)子串。例如n=k=3時(shí)只有4個(gè)串滿足條件：001, 011, 100, 110。

【分析】

首先，長度為a+2的回文，去掉兩端字符之后一定是長度為a的回文。也就是說，只要保證不包含長度為k和k+1的回文串，則一定不包含更長的回文串。

題目中k比較?。?i>k≤10），可以把長度為k的串作為一個(gè)整體，使用一個(gè)整數(shù)來記錄（≤1024），這樣可以直接使用位運(yùn)算。否則用字符串記錄，還需要做時(shí)間復(fù)雜度高得多的字符串運(yùn)算。

令F(i,b)表示已經(jīng)確定了從左到右的前i位，其中最右邊k位對應(yīng)的整數(shù)為b，剩下的n-i位上所有方案的個(gè)數(shù)。

首先引入以下變量：

（1）b₀=(b<<1)，表示b左移一位，然后右邊補(bǔ)0，得到的k+1位串。

（2）b₁=(b<<1)+1，表示b左移一位，然后右邊補(bǔ)1，得到的k+1位串。

（3）c₀=b₀& ((1<<k)-1)，表示取b₀最右邊k位得到的k位串。

（4）c₁=b₁& ((1<<k)-1)，表示取b₁最右邊k位得到的k位串。

c₀和c₁分別表示確定了第i+1位之后的最右邊k位串，分別對應(yīng)第i+1位為0和1兩種情況，則狀態(tài)轉(zhuǎn)移方程如下：F(i, b)=F(i+1,c₀)+F(i+1,c₁)。上述方程中，要求b₀、b₁、c₀、c₁不是回文，并且其最右邊k位也不是回文。

邊界條件是當(dāng)i=n時(shí)F=1。則最終答案就是ΣF(k,b),其中b是所有k位的非回文。算法的時(shí)間和空間復(fù)雜度均為O(n*2^k)。

完整程序如下：

習(xí)題9-12　保衛(wèi)Zonk（Protecting Zonk, ACM/ICPC Dhaka 2006, UVa12093）

給出一個(gè)n（n≤10000）個(gè)結(jié)點(diǎn)的無根樹。有兩種裝置A和B，每種都有無限多個(gè)。

（1）在某個(gè)結(jié)點(diǎn)X使用A裝置需要C1（C1≤1000）的花費(fèi)，并且此時(shí)與結(jié)點(diǎn)X相連的邊都被覆蓋。

（2）在某個(gè)結(jié)點(diǎn)X使用B裝置需要C2（C2≤1000）的花費(fèi)，并且此時(shí)與結(jié)點(diǎn)X相連的邊以及與結(jié)點(diǎn)X相連的點(diǎn)、相連的邊都被覆蓋。

求覆蓋所有邊的最小花費(fèi)。

【分析】

不難想到是樹形DP，考慮每個(gè)結(jié)點(diǎn)的覆蓋狀態(tài)。不妨把n=1作為樹根。令D(u,s)表示以結(jié)點(diǎn)u為根的子樹，當(dāng)前覆蓋狀態(tài)為s，所需的最小花費(fèi)。對于結(jié)點(diǎn)u，統(tǒng)稱其任意孩子為v，任意孫子為vx，u的父親為p，p的父親為px，u的任意兄弟結(jié)點(diǎn)統(tǒng)稱為ux。s分以下4種情況（參考圖2.54，虛線表示未覆蓋，實(shí)線已經(jīng)覆蓋s）：

（1）s=0：邊u-v，v-vx，u-p，p-px全部覆蓋。

（2）s=1：邊u-v，v-vx，u-p全部覆蓋。

（3）s=2：邊u-v，v-vx全部覆蓋。

（4）s=3：u-v，還有部分未覆蓋。

則所求答案為min(D(1,0),D(1,1),D(1,2))。從葉子到根結(jié)點(diǎn)從下往上每次一層進(jìn)行決策，則這個(gè)過程可以寫成dfs，狀態(tài)轉(zhuǎn)移的前提是u的孫子結(jié)點(diǎn)對應(yīng)的子樹已經(jīng)全部覆蓋。則狀態(tài)轉(zhuǎn)移過程如下：

（1）s=0：這種狀態(tài)一定要求u上放置一個(gè)B，v的狀態(tài)轉(zhuǎn)移方程式：D(u,0)= min(D(v,0),D(v,1),D(v,2),D(v,3)))。

（2）s=1：則要求v的覆蓋狀態(tài)≠3。要轉(zhuǎn)移到u的這種狀態(tài)有兩種可能：u上放一個(gè)A，或者且至少有一個(gè)v的覆蓋狀態(tài)=0。記w=(min(D(v,0),D(v,1),D(v,2)))，則D(u,1)=min((C1+w),w–min(D(v,0)–min(D(v,0),D(v,1),D(v,2)))。

（3）s=2：要轉(zhuǎn)移到這個(gè)狀態(tài)，就要求所有v的覆蓋狀態(tài)為1。D(u,2)= D(v,1)。

（4）s=3：則v的狀態(tài)可以是0、1、2其中之一。D(u,3)=w。

dfs中的循環(huán)次數(shù)剛好是所有的結(jié)點(diǎn)次數(shù)，所以算法的時(shí)間復(fù)雜度為O(n)。完整程序（C++11）如下：

習(xí)題9-14　圓和多邊形（Telescope, ACM/ICPC Tsukuba 2000, UVa1543）

給出一個(gè)圓和圓周上的n（3≤n≤40）個(gè)不同點(diǎn)，請選擇其中的m（3≤m≤n）個(gè)點(diǎn)，按照在圓周上的順序連成一個(gè)m邊形，使得它的面積最大。例如在如圖2.55所示的例子中，右上方的多邊形最大。

【分析】

假設(shè)總共有n個(gè)點(diǎn)。記D(i,j,k)為在第i～j個(gè)點(diǎn)中選擇k個(gè)點(diǎn)（其中必須包含i和j，0≤i<i+1<j<n），所能組成的最大的多邊形面積。對選擇的k個(gè)點(diǎn)中j之前的最后一個(gè)點(diǎn)x（i<x<j）進(jìn)行決策，則有D(i,j,k)=max(D(i,x,k-1)+area(i,x,j))，如圖2.56所示。其中，area(i,x,j)為i、x、j這3個(gè)點(diǎn)組成的三角形面積。所求結(jié)果為max(D(0,n,m))。算法的時(shí)間復(fù)雜度為O(n³)。

需要注意的是，需要預(yù)先把任意3個(gè)點(diǎn)組成的三角形面積計(jì)算出來，以便在遞推D時(shí)使用。完整程序如下：

習(xí)題9-15　學(xué)習(xí)向量（Learning Vector, ACM/ICPC Dhaka 2012, UVa12589）

輸入n個(gè)向量（x,y）（0≤x,y≤50)，要求選出k個(gè)，從(0,0)開始畫，使得畫出來的折線與x軸圍成的圖形面積最大。例如4個(gè)向量是(3,5)、(0,2)、(2,2)、(3,0)，可以依次畫(2,2)、 (3,0)、(3,5)，圍成的面積是21.5，如圖2.57所示。輸出最大面積的兩倍。1≤k≤n≤50。

【分析】

如果畫出來的折線形成凹多邊形，調(diào)整成凸多邊形一定面積更大（如圖2.58所示），所以任何最優(yōu)選擇中的k個(gè)向量一定是按照斜率從大到小依次選擇的。對所有向量按照斜率從大到小進(jìn)行排序?？紤]x可能為0，向量的斜率可以使用函數(shù)atan2(y, x)計(jì)算。

記F(i,c,h)為還要在i個(gè)向量中，還要選擇c個(gè)，畫出折線的最高y坐標(biāo)為h。后續(xù)還能再增加的最大面積（如圖2.59的淺色部分所示）。

狀態(tài)轉(zhuǎn)移方程：F(i,c,y)=max(F(i+1, c, y), F(i+1, c+1, y+v.y)+(2*y+v.y)*v.x)，其中v為第i個(gè)向量，有是否使用向量v的兩種決策。邊界條件為i=n,c=k時(shí)，F(xiàn)=0。所求結(jié)果為F(0,0,0)。算法的時(shí)間復(fù)雜度為O(50*n³)。

習(xí)題9-18　棒球投手（Pitcher Rotation, ACM/ICPC Kaosiung 2006, UVa1379）

你經(jīng)營著一支棒球隊(duì)。在接下來的g+10天中會有g（3≤g≤200）場比賽，其中每天最多一場比賽。你已經(jīng)分析出你的n（5≤n≤100）個(gè)投手中每個(gè)人對陣所有m（3≤m≤100）個(gè)對手的勝率（一個(gè)n*m矩陣），要求給出作戰(zhàn)計(jì)劃（即每天使用哪個(gè)投手），使得總獲勝場數(shù)的期望值最大。需要注意的是，一個(gè)投手在上場一次后至少要休息4天。

【分析】

每個(gè)投手上場一次至少休息4天，對于每場比賽來說，勝率最高的5個(gè)投手不可能前面4天都參加比賽（每天最多一場，每場只需1個(gè)投手），所以至少有1個(gè)休息夠了，可以只考慮勝率最高的5個(gè)人。

令DP(i,p0,p1,p2,p3)表示第i天，選擇對陣當(dāng)天對手勝率排名第p0的對手上場，且第i-x天選擇對應(yīng)排名第px的上場，前i天所能得到的最大得分。其中px=0則表示當(dāng)天無人上場。

狀態(tài)轉(zhuǎn)移時(shí)，首先要保證第i天選擇的對手不能和前面4天重復(fù)，然后對于每i天來說，有兩種情況：

（1）沒有比賽：則D(i,0,p1,p2,p3)=max(D(i-1,p1,p2,p3,p4)，其中0≤p4≤5。

（2）有比賽：則D(i,p0,p1,p2,p3)=max(D(i-1,p1,p2,p3,p4)+p)，對p0進(jìn)行決策，p是對當(dāng)天對手勝率排名p0的選手的勝率。

時(shí)間復(fù)雜度為O(g*5⁵⁾，因?yàn)槲寰S數(shù)組占用空間較大，需使用滾動數(shù)組，這樣空間復(fù)雜度就是常數(shù)O(2*6⁴)。完整程序如下：