課件動(dòng)態(tài)規(guī)劃

1、索引【 POJ1141 】括號(hào)序列【 POJ1191 】棋盤(pán)分割【 SPOJ196 】決斗【 AOA 】跳舞機(jī)【 AOA 】積木【 AOA 】藝術(shù)館的火災(zāi)【 AOA 】人的名字【 UVa10559 】方塊消除索引【 AOA 】公路巡邏【 POJ1074 】并行期望值【 AOA 】高性能計(jì)算機(jī)【 AOA 】模板匹配【 AOA 】不可的編碼【 AOA 】青蛙的煩惱【 AOA 】排列問(wèn)題【 AOA 】最優(yōu)排序二索引【 POJ1038 】Bugs 公司【 UVa10531 】迷宮統(tǒng)計(jì)【 AOA 】貪吃的九【 AOA 】【 AOA 】移的蜜月器人【 UVa10271 】佳佳的筷子【 AOA 】偷懶的工人

2、【 AOA 】鐵路調(diào)度索引【 POJ1691 】平板涂色【 POJ1947 】道路重建【 ZJU【 AOA 】圓和多邊形落地【 UVA10118 】糖果【 AOA 】丟三落四的老鼠【 AOA 】最長(zhǎng)公共子序列問(wèn)題【 UVA10635 】排列的 LCS 問(wèn)題索引【 UVA【 UVA】最長(zhǎng)上升子序列問(wèn)題】最優(yōu)二分檢索樹(shù)問(wèn)題【 POJ1180 】任務(wù)調(diào)度問(wèn)題【 AOA 】序列分割問(wèn)題【 AOA 】多排列的 LCS【 POJ1159 】回文詞【 AOA 】友好城市【 POJ1160 】郵局索引【 AOA 】串【 POJ1946 】奶牛轉(zhuǎn)圈【 AOA 】元件折疊【 AOA 】DNA 序列【 AOA 】最

3、優(yōu)布車(chē)方案括號(hào)序列定義如下規(guī)則序列（字符串）：空序列是規(guī)則序列；如果 S 是規(guī)則序列，那么（ S ）和 S 也是規(guī)則序列；如果 A 和 B 都是規(guī)則序列，那么 AB 也是規(guī)則序列。例如，下面的字符串都是規(guī)則序列： () ， ，() ，() ，() ，()()這幾個(gè)則不是規(guī)則序列： ( ， ， ，)( ，()現(xiàn)在，給出一些由 ( ， ) ， ， 的序列，請(qǐng)?zhí)砑颖M量少的括號(hào)，得到一個(gè)規(guī)則序列。分析di,j:子串 ij 最少需要添加的括號(hào)數(shù)狀態(tài)轉(zhuǎn)移 S 形如 (S) 或者 S: di+1,j-1 S 形如 (S 或者 S: di+1,j+1 S 形如 S) 或者 S: di,j-1+1 長(zhǎng)度大于 1

4、: di,k+dk+1,j (i<=k<=j-1)狀態(tài) O(n2),轉(zhuǎn)移 O(n),共 (n3)棋盤(pán)分割將一個(gè) 8×8 的棋盤(pán)進(jìn)行的分割：將原棋盤(pán)割下一塊矩形棋盤(pán)并使剩下部分也是矩形，再將剩下的部分繼續(xù)如此分割(n-1) 次后，連同最后剩下的矩，這樣形棋盤(pán)共有 n （ n<15 ）塊矩形棋盤(pán)（每次切割都只能沿著棋盤(pán)格子的）。棋盤(pán)分割原棋盤(pán)上每一格有一個(gè)分值，一塊矩形棋盤(pán)的總分為其所含各格分值之和?，F(xiàn)在需要把棋盤(pán)按上述規(guī)則分割成 n 塊矩形棋盤(pán)，并使各矩形棋盤(pán)總分的均方差最小。(a)的分割方案(b) 不的分割方案分析變形均方差公式nnn11n2222(n(x)ni )

5、xi(x)i 1i 1i 1平均值是一定的（等于所有和除以 n ）的數(shù)的只需要讓每個(gè)矩形總分的平方和盡量小分析考慮左上角坐標(biāo)為 (x1,y1) ，右下角坐標(biāo)為(x2,y2) 的棋盤(pán)，設(shè)它把切割 k 次以后得到的k+1 塊矩形的總分平方和最小值為dk,x1,y1,x2,y2狀態(tài)轉(zhuǎn)移 :沿著某橫線(xiàn)切或者豎線(xiàn)切，然后選一塊繼續(xù)切 ,如橫著切的兩類(lèi)決策是 dk-1,x1,y1,a,y2+sa+1,y1,x2,y2 dk-1,a+1,y1,x2,y2+sx1,y1,a,y2 其中x1<=a<=x2分析狀態(tài) dk,x1,y1,x2,y2設(shè) m 為棋盤(pán)邊長(zhǎng)，則狀態(tài)數(shù)目為 m4n ，決策數(shù)目為 O

6、(m)轉(zhuǎn)移時(shí)間取決于計(jì)算 sx1,y1,x2,y2 的時(shí)間預(yù)處理先用 O(m2) 時(shí)間算出左上角為 (1,1)的所有矩陣元素和，這樣狀態(tài)轉(zhuǎn)移時(shí)間就是 O(1) ，總的時(shí)間復(fù)雜度為 O(m5n)決斗編號(hào)為 1n 的 n 個(gè)人按逆時(shí)針?lè)较蚺懦梢蝗?，他們要決斗 n-1 場(chǎng)。每場(chǎng)比賽在某相鄰兩人間進(jìn)行，敗者圈子，緊靠敗者右邊的人成為與勝者直接相鄰的人。任意兩人之間決斗的勝負(fù)都將在一矩陣中給出（如果 Ai,j=1 則 i 與 j 決斗 i 總是贏， 如果 Ai,j=0 則 i 與 j 決斗時(shí) i 總是輸），求出所有可能贏得整場(chǎng)決斗的人的序號(hào)分析di,j 表示是否有可能 i 和j 相遇 ,則第i 個(gè)人能取

7、得最后的勝利當(dāng)且僅當(dāng) di,i 為 true狀態(tài)轉(zhuǎn)移 :考慮相遇前的最后一步 , 則dI,j 為 true 當(dāng)且僅當(dāng) 能找到一個(gè) k,使得 i 能遇 k, k 能遇到j(luò),且 i 或者 j 能打敗 k狀態(tài)有 O(n2) 個(gè),轉(zhuǎn)移有 O(n) 個(gè),共 O(n3)跳舞機(jī)DDR 的主要內(nèi)容是用腳來(lái)踩踏板。踏板有 4 個(gè)方向的箭頭，用 1 ， 2 ， 3 ， 4 來(lái)代表每首歌曲有一個(gè)箭頭序列， 者必須按照這個(gè)序列依次用某一只腳踩相應(yīng)的踏板。在任何時(shí)候，兩只腳都不能 在同一個(gè)踏板上，但可以同 時(shí)待在中心位置 0 。跳舞機(jī)每一個(gè)時(shí)刻，必須移動(dòng)而且只能移動(dòng)一只腳去踩相應(yīng)的箭頭，另一只腳不許移動(dòng)。跳 DDR 會(huì)

8、消耗體力。從中心移動(dòng)到任何一個(gè)箭頭耗費(fèi) 2 單位體力，從任何一個(gè)箭頭移動(dòng)到相鄰箭頭耗費(fèi) 3 單位體力，移動(dòng)到相對(duì)的箭頭（ 1 和 3 相對(duì)， 2 和 4 相對(duì)） 耗費(fèi) 4 單位體力，而留在原地再踩一下只需要 1 單位。給定一首舞曲 ,每個(gè)箭頭應(yīng)該用哪只腳踩才能使體力消耗最少呢？例如對(duì)于序列LLUR,用 LLRR 腳去踩，總的體力耗費(fèi)為2 + 1 + 2 + 3 = 8 單位分析目前左腳在位置 x,右腳在位置 y,從第 k個(gè)箭頭開(kāi)始跳 ,則最少體力耗費(fèi)為 dx,y,k, 用左腳 , dak, y, k+1 + effort(x, ak) 用右腳 , dx, ak, k+1 + effort(y,

9、 ak)狀態(tài)是 O(n) 的，決策是 O(1) 的,復(fù)雜度為 O(n)總時(shí)間積木有 N 塊編號(hào)依次為 1 ， 2 ， N 的長(zhǎng)方體積木。每塊積木有三條不同邊分別稱(chēng)為 a 、 b 、 c 邊acb從積木中選出若干塊分成 M 堆,每堆至少有 1 塊積木，并且第 K 堆中任意一塊積木的編號(hào)要大于第 K+1 堆中任意一塊積木的編號(hào)積木每一堆積木要垂直摞成一根柱子 , 并滿(mǎn)足 除最頂上的一塊積木外，任意一塊積木的上表面同且僅同另一塊積木的下表面接觸，并且要求下面積木的上表面能包含上面的積木的下表面，也就是說(shuō)，要求下面積木的上表面兩對(duì)邊的長(zhǎng)度分別大于等于上面積木兩對(duì)邊的長(zhǎng)度。 對(duì)于任意兩塊上下表面相接觸的

10、積木，下面積木的編號(hào)要小于上面積木的編號(hào)要求每堆積木的高度和盡量大分析我們從最后一堆積木開(kāi)始 ,慮記 di,a,b,k 為已經(jīng)用了前 a 個(gè)積木得到了 i一個(gè)個(gè)積木考根柱子 ,目前頂面為積木 b 的第k 個(gè)面 ,以后還能獲得的最大高度 ,有三類(lèi)決策 新起一堆 , di+1,a+1,a+1,k, 當(dāng)i<m 時(shí)合法 加在當(dāng)前堆 , di,a+1,a+1,k,當(dāng)放得上時(shí)合法 丟棄當(dāng)前塊 , di,a+1,b,k,隨時(shí)合法狀態(tài) O(n2m) 個(gè),O(n2m)決策 O(1),總時(shí)間藝術(shù)館的火災(zāi)藝術(shù)館著火了 .這是一幢兩層的小樓，每層有 N個(gè)房間，用兩個(gè)數(shù)分別表示藝術(shù)品價(jià)值和火勢(shì) .滅火器最多只能發(fā)

11、射 K 次，每次發(fā)射將覆蓋一個(gè)矩形的區(qū)域（矩形的高度可以是 1 也可以是 2 ），所到之處不但火焰會(huì)被撲滅，藝術(shù)品也被摧毀。你需要決定滅火器每次應(yīng)該怎樣發(fā)射，才能將這次火災(zāi)的損失降到最低限度。損失等于摧毀的藝術(shù)品總價(jià)值加上剩余的火勢(shì)總值40/5050/4030/5060/7030/4030/5040/2020/30分析模型：在一個(gè) 2×N 的矩陣中，找出 K 個(gè)子矩陣。矩陣的每個(gè)元素有兩個(gè)值 V 和F 。題目要讓 K 個(gè)子矩陣的 V 值和其他矩陣的F 值之和最小，而如果我們令 W=V-F ，則目標(biāo)轉(zhuǎn)換為讓K 個(gè)子矩陣元素的 W 值之和最小矩陣可以重疊，這給解題帶來(lái)不便。我們可以不考慮

12、重疊情況，分析用區(qū)域 (i,j) 來(lái)表示“第一行第 i 個(gè)格子右邊所有元素加上第二行第 j 個(gè)格子右邊的所有元素”這個(gè)區(qū)域，用 ds,i,j 來(lái)表示在這個(gè)區(qū)域中選擇 s 個(gè)子矩陣，它們的元素總和的最小值狀態(tài)轉(zhuǎn)移的決策是新矩形的放置 ,有三類(lèi)第一行第 i 個(gè)格子不用 , ds,i+1,j在第一行從第 i 個(gè)格子開(kāi)始放矩形 ,到ds-1,i+L,j設(shè)長(zhǎng)度為 L,轉(zhuǎn)移 i=j 時(shí)還可放置寬度為 2 的矩形 ,轉(zhuǎn)移到 ds-1, i+L, j+L狀態(tài) O(kn2) 個(gè),決策O(n),轉(zhuǎn)移時(shí)間 O(1)( 先預(yù)處理 ), 總時(shí)間 O(kn3)人的名字考慮一種基于重復(fù)子串的壓縮方法用Stk 表示 k 個(gè)相

13、同的子串 St( 其中 St 稱(chēng)為重復(fù)子串， k 是一個(gè)單字節(jié)整數(shù)，只占一個(gè)字符位置 ) 如果這 k 個(gè)子串并沒(méi)有連在一起，則可以在 Stk 的后面加上 S1t1S2 t2Srtr （ 1<ti<k ， ti<ti+1 ），表示在第 ti 個(gè) St 的后面放置 Si ， Si 稱(chēng)為子串St 和 Si 也都可以是壓縮后的字符串比如I_am_WhatWhat_is_WhatWhat 的壓縮結(jié)果為I_am_What4_is_2 ，長(zhǎng)度為 19 ( 例子中的空格用下劃線(xiàn)“ _” 表示，數(shù)字 2 和 4 實(shí)際上是用單字節(jié)二進(jìn)制表示的 )名字以空格開(kāi)始或結(jié)尾，大小寫(xiě)敏感分析令 da,b

14、表示以 a, b 為起止位置的串 ( 記為Sa,b) 的最短壓縮長(zhǎng)度 ,狀態(tài)轉(zhuǎn)移則目標(biāo)為 d1,L 連接: da,b = minda,i + di+1,b, a<=i<b 壓縮 :需要確定重復(fù)子串 .當(dāng)重復(fù)子串很多時(shí),決策枚舉的代價(jià)較大來(lái)枚舉 !壓縮決策可以通過(guò)動(dòng)態(tài)分析ga,b,c 表示將串 Sa,b,選擇長(zhǎng)度為 c 的重復(fù)子串進(jìn)行壓縮得到的最短長(zhǎng)度 . 枚舉串( 可能為空 ) 的下一個(gè)位置 i, 狀態(tài)轉(zhuǎn)移方程為gi, b, cgi, b, ciacc, iga, b, cminac i b c 1Sa,ac 1 Si,ic 1da13iac分析邊界條件ba1cba1或者Sa, a

15、c1Sbc1, bga, b, c2bda, b3ca1da,b 的狀態(tài)轉(zhuǎn)移方程minda, i + di +1, ba i <bda, b = minmin ga, b, i1 i b -a +1是否有Sa, a+c-1=Si, i+c-1?如何較快的從 c=1 開(kāi)始遞推 ,總O(L3)分析時(shí)間 :空間預(yù)處理 O(L3),O(L4),共 O(L4) g:本來(lái)是三維的 O(L3) 的,但注意到在每個(gè)式故以 b 為階段遞推子里b 參量沒(méi)有發(fā)生變化 ,只需要 O(L2) 的空間 預(yù)處理結(jié)果 :如果用 ha,b,c 表示是否有 Sa,a+c-1=Sb, b+c-1,則又是三維的 .可以用鏈,用

16、 nexta,b 表示子串 Sa,b 的下一個(gè)式相同子串的開(kāi)始位置 ,則只需要 O(L2) 的空間方塊消除n 個(gè)帶顏色排成一列，相同顏色的方塊連成一個(gè)區(qū)域（如果兩個(gè)相鄰方塊顏色相同，則這兩個(gè)方塊屬于同一區(qū)域）時(shí)，你可以任選一個(gè)區(qū)域消去。設(shè)這個(gè)區(qū)域包含的方塊數(shù)為 x ，則將得到 x2 分方塊消去之后將產(chǎn)生空列 ,此時(shí)其右邊的所有方塊就會(huì)向左移 ,一起直到所有連在方塊消除下面是一個(gè)的例子分析輸入表示成兩個(gè)長(zhǎng)度為 L 的數(shù)組 color 和len L 表示有多少“段”不同的顏色方塊 colori 表示第 i 段的顏色 leni 表示第 i 段的方塊長(zhǎng)度題目的例子成 color=1,2,3,1, le

17、n=1,4,3,1用 (i,j,k) 表示在第 ij 段方塊的右邊添加 k個(gè)顏色為 colorj 的方塊后得到的方塊序列 ,相當(dāng)于考慮第 ij 段,但讓 lenj 的值增加 k分析d i,j,k 表示把序列 (i,j,k) 消除的最大得分考慮最后一段，有兩類(lèi)決策 如果馬上消掉，就是 di,j-1,0+(lenj+k)2 ； 如果和前面的若干段一起消，設(shè)這“若干段”是 p(i<=p<j) ，得分為中最后面的di,p,k+lenj+dp+1,j-1,0, colorp=colorj邊界條件是 f i,i-1,0=0其中時(shí)間 O(n4),建議用記憶化遞歸實(shí)現(xiàn)公路巡邏在一條沒(méi)有分岔的公路上

18、有 n （ n50 ）個(gè)關(guān)口，相鄰兩關(guān)口之間的距離是 10km 。所有車(chē)輛在公路上的最低速度為 60km/h ，最高速度為120km/h ，且只能在關(guān)口處改變速度。有 m(m300) 輛巡邏車(chē)分別在時(shí)刻 Ti 從第 ni 個(gè)關(guān)口出發(fā)，勻速行駛到達(dá)第 ni+1 個(gè)關(guān)口，路上耗費(fèi)時(shí)間為 ti(s) 。兩輛車(chē)相遇指他們之間發(fā)生超車(chē)現(xiàn)象或同時(shí)到達(dá)某個(gè)關(guān)口。求一輛于 6 點(diǎn)整從第 1 個(gè)關(guān)口出發(fā)去第 n 個(gè)關(guān)口的車(chē)最少會(huì)與多少輛巡邏車(chē)相遇，以及在此情況下到達(dá)第 n 個(gè)關(guān)口的最早時(shí)刻。所有車(chē)輛到達(dá)關(guān)口的時(shí)刻必須是整秒。分析di,T 表示在時(shí)刻 T 到達(dá)第 i 個(gè)關(guān)口的途中與巡邏車(chē)最少相遇次數(shù)，狀態(tài)轉(zhuǎn)移方程

19、為di,T mindi1,Ttwi1,Tt,T 300t600函數(shù) wi-1,T-t,T 是目標(biāo)時(shí)刻 T-t 從第 i-1 個(gè)關(guān)口出發(fā)，于時(shí)刻 T 到達(dá)第 i 個(gè)關(guān)口途中與巡邏車(chē)相遇的次數(shù)設(shè)每?jī)蓚€(gè)關(guān)口間行駛時(shí)間有 k 種選擇 ,狀態(tài)總數(shù)為 O(kn2) ，決策數(shù)目為 O(k) ，轉(zhuǎn)移時(shí)間依賴(lài)于w分析方法一：在每個(gè)決策中都進(jìn)行一次計(jì)算，對(duì)所有從第 i 個(gè)關(guān)口出發(fā)的巡邏車(chē)進(jìn)行，由于每輛巡邏車(chē)恰好被一次，故這樣每個(gè)狀態(tài)的計(jì)算w 的平均時(shí)間復(fù)雜度為 O(m/n) ，算法總時(shí)間復(fù)雜度為 O(kn2)×O(k)×O(m/n)=O(k2nm) 。方法二：仔細(xì)觀(guān)察狀態(tài)轉(zhuǎn)移方程可以發(fā)現(xiàn)，在對(duì)

20、狀態(tài) di,T 進(jìn)行轉(zhuǎn)移時(shí)，所計(jì)算的函數(shù) w 都是從第 i 個(gè)關(guān)口出發(fā)的，而且出發(fā)時(shí)刻都是 T ，只是相應(yīng)的到達(dá)時(shí)刻不同。能否考慮這些車(chē)之間的聯(lián)系，從而利用已經(jīng)得出的結(jié)果，減少重復(fù)運(yùn)算呢？分析令 gk=wi,T,k+1-wi,T,k,設(shè)到達(dá)時(shí)間為 k和 k+1 的目標(biāo)車(chē)分別為車(chē) A 和車(chē) B對(duì)于每輛從第 i 個(gè)關(guān)口出發(fā)的巡邏車(chē) C ，設(shè)其出發(fā)和到達(dá)時(shí)刻分別為 St 和 Tt ，則 Tt<k 或 Tt>k+1 ，車(chē) A 車(chē)B 與車(chē) C 的相遇情況相同 Tt=k ，則車(chē) A 與車(chē) C 相遇，車(chē) B 的分析又分為，若 St<=T ，則車(chē) B 不與車(chē) C 相遇，否則車(chē)B 也與車(chē) C

21、相遇 Tt=k+1, 則車(chē) B 與車(chē) C 相遇，對(duì)車(chē) A 的分析又分為，若 S <=T ，則車(chē) A 不與車(chē) C 相遇，否則分析綜合起來(lái) gk=G(Tt=k+1)&&(St<=T)G(Tt=k)&& (St<=T) G(P) 表示所有從關(guān)口 i 出發(fā)且滿(mǎn)足條件 P 的巡邏車(chē)數(shù)目計(jì)算 di,T 時(shí)先對(duì)所有從第 i 個(gè)關(guān)口出發(fā)的巡邏車(chē)進(jìn)行一次掃描 ,求出 wi,T,T+300 的同時(shí)求出 gT+301.T+600 ，時(shí)間復(fù)雜度為 O(m/n)以后的轉(zhuǎn)移中，由 wi,T,k+1=wi,T,k+gk ，僅需O(1) 時(shí)間就可以求出函數(shù)值 w ，狀態(tài)轉(zhuǎn)移時(shí)

22、間僅為O(1)總時(shí)間 O(kn2)*(O(m/n)+k*O(1)=O(knm+k2n2)并行期望值考慮一個(gè)可以并行執(zhí)行兩個(gè)高級(jí)語(yǔ)言程序的。高級(jí)語(yǔ)若干條賦值指令組成，形式是： < 變量 > := < 運(yùn)言算數(shù) 1> op < 運(yùn)算數(shù) 2>變量名由不超過(guò) 20 個(gè)字母組成。運(yùn)算數(shù)是變量名或小于100 的正整數(shù)。 op 是運(yùn)算符，可以是加號(hào)“ +” 或者減號(hào)“ -”執(zhí)行前,語(yǔ)言。 X := Y + Z 翻譯成程序被翻譯成Mov R1, Y Mov R2, Z Add R1, R2 Mov X, R1Mov 指令把第二個(gè)操作數(shù)送到第一個(gè)中去， Add 操作進(jìn)行加法，

23、并把結(jié)果保存在第一個(gè)操作數(shù)中。注意 Y 和Z 代表變量或者整數(shù)常量。 X := Y - Z 的語(yǔ)言代碼類(lèi)似并行期望值處理器接受了兩個(gè)語(yǔ)言程序后，每次隨機(jī)選一個(gè)程序，執(zhí)行它的下一條指令。如果某個(gè)程序畢，處理器會(huì)連續(xù)把另一個(gè)程序。兩個(gè)程序共享所有變量（一開(kāi)始的時(shí)候各個(gè)變量的值均為 0 ），但擁有兩個(gè)R2的寄存器R1 和由于執(zhí)行順序不確定，最后各個(gè)變量的值也是不確定的。不過(guò)，可以計(jì)算出每個(gè)變量在所有情況下最終值的平均數(shù)（即并行期望值）。現(xiàn)在給你兩個(gè)高級(jí)語(yǔ)言程序，請(qǐng)編程算出所有變量的并行期望值。每個(gè)高級(jí)語(yǔ)言程序最多有 25 條指令，兩個(gè)程序最多共使用 10 個(gè)變量。分析語(yǔ)言 ,首先把高級(jí)語(yǔ)言程序翻譯成

24、 <Rx1> := < 運(yùn)算數(shù) 1> + <0> <Rx2> := < 運(yùn)算數(shù) 2> + <0> <Rx1> := <Rx1> op <Rx2> < 變量 > := <Rx1> + <0>翻譯規(guī)則其中x 是程序代號(hào).即一共有四個(gè)寄存器 : R11,R12, R21, R22,和普通變量同等對(duì)待dx,y,k 表示程序 1x 條指令 ,程序 2 執(zhí)行完y 條指令后變量 k 的并行期望值分析情況一 :指令第 1 個(gè)程序的第 x 條剛剛 該指令不是在給 k 賦

25、值,等于 dx-1,y,k 指令形如 <k>:=<a> op <b>, dx-1,y,b 記這個(gè)結(jié)果為 K1等于 dx-1,y,a op情況二 :條指令 ,的是第 2 個(gè)程序的第 y剛剛按同樣的方法可計(jì)算出 K2情況一的概率是 x/(x+y),情況二是 y/(x+y)按期望公式 , dx,y,k=(x*K1+y*K2)/(x+y)分析為什么在情況一的賦值語(yǔ)句后 , k 的期望等于 dx-1,y,a op dx-1,y,b?質(zhì)為什么情況一的概率是 x/(x+y), y/(x+y)?期望的線(xiàn)性性情況二是 狀態(tài) (x-1, y) 和(x, y-1) 的概率比為到達(dá)

26、兩個(gè)狀態(tài)的路徑條數(shù)比 ,即 C(x+y-1,x-1)/C(x+y-1,y-1),展開(kāi)得 (x+y-1)!/(x-1)!y!/(x+y-1)!/x!(y-1)!=x/y高性能計(jì)算機(jī)一個(gè)大型計(jì)算任務(wù)可以劃分成很多 A 類(lèi)任務(wù)和 B類(lèi)任務(wù) .所有 A 類(lèi)任務(wù)都相同 ,所有 B 類(lèi)任務(wù)都相同.所有任務(wù)的相對(duì)執(zhí)行順序沒(méi)有要求有 p 個(gè)計(jì)算結(jié)點(diǎn) ,對(duì)于第 i 個(gè)結(jié)點(diǎn)三種工作狀態(tài)：待機(jī)、 A 類(lèi)和 B 類(lèi)。初始為待機(jī)狀態(tài)，從其他的狀態(tài)轉(zhuǎn)入 A 或 B 狀態(tài)分別需要 tiA 和 tiB 的時(shí)間連續(xù)處理 x 個(gè) A 類(lèi)子任務(wù)，時(shí)間為 t = kiAx2 ；類(lèi)似定義kiB你需要進(jìn)行任務(wù)分配 ,即給每個(gè)結(jié)點(diǎn)設(shè)置任務(wù)

27、隊(duì)列.隊(duì)列中一串連續(xù)的同類(lèi)子任務(wù)不能被分成兩部分執(zhí)行。所有結(jié)點(diǎn)都同時(shí)開(kāi)始運(yùn)行，目標(biāo)是最分析該問(wèn)題可以分成兩個(gè)子問(wèn)題： 計(jì)算第 i 個(gè)結(jié)點(diǎn)完成 ai的最短時(shí)間個(gè) A 任務(wù)和 bi個(gè) B 任務(wù) 給第 i 個(gè)結(jié)點(diǎn)分配 ai個(gè) A 任務(wù)和 bi 個(gè) B 任務(wù)，取所有結(jié)點(diǎn)運(yùn)行時(shí)間的最大值問(wèn)題 1 的解決 :讓 di,t,a,b 表示結(jié)點(diǎn) i ，還有 a 種 A 任務(wù)和 b 種 B 任務(wù)，并且當(dāng)前需要執(zhí)行t 類(lèi)任務(wù)（ t=A 或 B ）所需要的最短時(shí)間分析決策為當(dāng)前執(zhí)行 j 個(gè)連續(xù)序列 ,di,A,a,b=mindi,B,a-j,b+ti +ki *j AA2問(wèn)題 1 的解 fi,a,b=mindi,A,

28、a,b, di,B,a,b問(wèn)題 2 是任務(wù)分配問(wèn)題 . gi,a,b 代表前 i 個(gè)結(jié)點(diǎn)完成 a 個(gè) A 任務(wù) b 個(gè) B 任務(wù)的最短時(shí)間，決策為給任務(wù) i 分配 j 個(gè)A 任務(wù)和 k 個(gè)B 任務(wù) ,fi,j,k 即 gI,a,b=min maxdi-1,a-j,b-k,時(shí)間 O(pna nb ),22空間 O(nanb),如何優(yōu)化?模板匹配* 代表零個(gè)或多個(gè)字符。通配符 Q 稱(chēng)兩個(gè)通配符P1 和 P2 的公共模板，如果被 Q 匹配的字符串一定同時(shí)被二者匹配。如 ba*ab 是 *ab* 和 ba*b 的公共模板P1 、 P2 的一個(gè)模板集合 Q1 ， Q2 ， Qn 稱(chēng)為完備的，如果每個(gè) Q

29、i 都是 P1 、 P2 的公共模板， 且任何一個(gè)既能被 P1 匹配又能被 P2 匹配的字符串至少能被一個(gè) Qi 匹配給出 P1 ， P2 ，求模板數(shù)目最少的完備模板集合例如，對(duì)于 ba*ab 和 *ab* ，一個(gè)包含最少數(shù)目模板的完備集合為： ba*ab*bbab*bba*abbab分析如果把一個(gè)模板看作一個(gè)集合（即它能匹配到所有字符串集合），則模板包含關(guān)系等同于集合包含關(guān)系本題的任務(wù)是求 P1 和P2 的交集的最小覆蓋( 即這些集合的并為 P1 和P2 的交,數(shù)目應(yīng)盡量小 )且集合基本思想 :枚舉每一個(gè)種同時(shí)被兩個(gè)模板匹配的串 s ，對(duì)每種情況都構(gòu)造一個(gè)模板去覆蓋它分析問(wèn)題 (i,j) 表

30、示需要匹配 P1 從第 i 位起的剩下串和 P2從第 j 位起的剩下串，狀態(tài)轉(zhuǎn)移有四種情況：a* 和 b* 沒(méi)有交集，因?yàn)闊o(wú)論公共串 s 的第一位是什么都不行。a*b 和 ab* 有交集，且公共串 s 的第一位只有一種情況： a ，剩下的任務(wù)是要讓 s 從第 2 位起同時(shí)匹配 *b 和 b* 。轉(zhuǎn)移到(i+1,j+1) 。a*b 和 *ab 有交集，且 s 的第一位必須是 a 。顯然對(duì)于 P1 來(lái)說(shuō)還需要匹配 *b ，但是對(duì)于 P2 來(lái)說(shuō)，可以匹配 ab ，也可以匹配*ab ，甚至可以匹配 b 。則 (i,j) 轉(zhuǎn)化為了 (i+1,j) 、(i+1,j+1) 和(i+1,j+2)*ab 和 *

31、b 有交集，且 s 的第一位隨便是什么都可以，用 * 表示，為什么）?，F(xiàn)在狀態(tài)轉(zhuǎn)移到了什么地方呢？是 (i+1,j)（想和(i,j+1)好象有點(diǎn)亂.掉一個(gè)字符仔細(xì)分析后兩種情況 , * 可以看為空或者吃不可的編碼給定 n(n20) 個(gè) 01 編碼串 S1,S2,Sn ，尋找一個(gè)編碼串 T ，至少可被分解為兩種不同的 Si 的排列例如：給定 5 個(gè) 01 編碼串：S1=0110 ， S2=00 ， S3=111 ， S4=001100 ，S5=110 。一個(gè)符合要求的編碼串 T 是：001100110 ，兩種分解方法為 00+110(S2+S5+S1) 001100+110 (S4+S5)而 0

32、110110 只有一種分解方法(S1+S5)0110+110分析先考慮搜索策略。搜索的關(guān)鍵是編碼串 T 至少存在兩種不同的分解方法。從搜索分解方法出發(fā)，同時(shí)搜索兩種分解方法，可以大大減少搜索量。分析整的分解方案所無(wú)法匹配的剩余部分，一定是某個(gè) S 編碼串的后綴。14243B1442443A定義狀態(tài) di,j 為：當(dāng) B 部分為第 i 個(gè)數(shù)字串從第j+1 開(kāi)始的后綴時(shí)， A 部分的最短長(zhǎng)度邊界:di,j=j,當(dāng)存在某個(gè)長(zhǎng)度為 j 的串為串 i 的前綴時(shí)其他 di,j 為無(wú)窮大分析只考慮 B.轉(zhuǎn)移和 A 無(wú)關(guān),從某個(gè)狀態(tài) di,j出發(fā)進(jìn)行轉(zhuǎn)移，可以分為兩種情況： 某串 k 是 B 的前綴，則用 d

33、i,j+Lk 更新di,j+Lk B 是某串k 的前綴, dk,Li-j則用 di,j+Li-j 更新分析因?yàn)轭}目要求找出的串是長(zhǎng)度最短且在同長(zhǎng)度的串中字典序最小的一個(gè)，因此，若長(zhǎng)度不等時(shí)， 可以直接取小的那個(gè)；若長(zhǎng)度相等，則要追溯前面的狀態(tài)，取字典序較小的那個(gè)。這與一般的動(dòng)態(tài)是不太相同的，需要特別注意為了編程方便，可以采用記憶化搜索的方式。另外，由于程序中需要大量用到查找某個(gè)字符串是否存在的操作，為了提高程序效率，可以用 Trie的結(jié)構(gòu)來(lái)青蛙的煩惱池塘里有 n 片荷葉（ 1n1 000 ），它們正好形成一個(gè)凸多邊形。按照順時(shí)針?lè)较驅(qū)⑦@ n 片荷葉順次編號(hào)為 1 ， 2 ， n 。有一只小青蛙

34、站在 1 號(hào)荷葉上，它想跳過(guò)每片荷葉一次且僅一次（它可以從所站的荷葉跳到另外任意一片荷葉上）。同時(shí)， 它又希望跳過(guò)的總距離最短。請(qǐng)你編程幫助小青蛙設(shè)計(jì)一條路線(xiàn)。分析最短的路線(xiàn)中不存在相交的邊。證明 :路線(xiàn)變換（實(shí)線(xiàn)表示一步到達(dá)，虛線(xiàn)多步）根據(jù)這個(gè)結(jié)論可以知道：從 1 出發(fā)第一步只能到 2 或者 n 。如果第一步到了 2 ，則第二步只能到 n 或者 3，因?yàn)檫叢荒芟嘟?！1CCBBAA分析任意時(shí)刻沒(méi)有經(jīng)過(guò)的頂點(diǎn)區(qū)間設(shè) ds,L,0 表示從 s 出發(fā)，遍歷 ss+L-1中的頂點(diǎn)一次且僅一次的最短距離；ds,L,1 表示從 s+L-1 出發(fā)，遍歷 ss+L- 1 中的頂點(diǎn)一次且僅一次的最短距離。容易

35、寫(xiě)出狀態(tài)轉(zhuǎn)移方程 ,時(shí)空均為 O(n2)排列問(wèn)題在整數(shù) 1 ， 2 ， N 的排列中，有些排列滿(mǎn)足性質(zhì) A ：該排列中除了最后一個(gè)整數(shù)以外的每一個(gè)整數(shù)后面有（不必直接緊跟）一個(gè)同它相差為 1 的整數(shù)。例如： N = 4 ，排列 1432 是具有性質(zhì) A 的，而 2431 則不滿(mǎn)足。設(shè)有一個(gè) N 個(gè)數(shù)的排列，已知其中 P(PN) 個(gè)位置上的數(shù)，求共有多少個(gè)這樣的排列在 P 個(gè)位置上具有已知的數(shù)，且具有上述性質(zhì) A 。例如： N = 4 ，且已知第 1 位、第 2 位分別是 1 和4 ，則 1432 ， 1423 就是這樣的兩個(gè)排列。分析通過(guò)枚舉 N 比較小的時(shí)候滿(mǎn)足題目的排列，發(fā)現(xiàn)一個(gè)規(guī)律：任何

36、一個(gè)排列的后 k 位（ lkn ）是若干連續(xù)整數(shù)組成的集合?？梢杂脭?shù)學(xué)歸納法證明這個(gè)結(jié)論進(jìn)一步地，還可以證明只要滿(mǎn)足任意后 k 位（ lkn ）是若干連續(xù)整數(shù)組成的集合， 則這個(gè)排列一定符合題目要求。下面給出時(shí)空復(fù)雜度均為 O(n2) 的算法分析設(shè) ds, r 表示滿(mǎn)足下面條件的序列 C 的總數(shù) 為 s, s+1s+r-1 的一個(gè)排列 任意后 k 位都是連續(xù)整數(shù)組成的集合如果原問(wèn)題中倒數(shù)第 i 個(gè)位置上的數(shù)已經(jīng)確定為 x （ lir ），那么 C 的倒數(shù)第 i 個(gè)位置上d的s+1數(shù),r-也1，要是 x 。倒數(shù)由第加r 位法必原須為理s得ds,r-1，倒數(shù)第 r 位必須為 s+r-1ds,r=d

37、s,r-1+ds+1,r-1， 倒數(shù)第 r 位不確定0其他情況，不能保證后 r-1 位為連續(xù)整數(shù)，故無(wú)解最優(yōu)排序二邊長(zhǎng)為 3 的正三角形分成三層共 9 個(gè)小的正三角形，把它們從頂?shù)降?，從左到右?19 編號(hào)。邊長(zhǎng)為 n 的正三角形可以劃分成 n2 個(gè)三角形。四個(gè)這樣的邊長(zhǎng)為 n 的正三角形可以組成一個(gè)三棱錐。將正三棱錐的三個(gè)側(cè)面依順時(shí)針次序 ( 從頂向底視角 ) 編號(hào)為 A, B, C ，底面編號(hào)為 D 。右圖為展開(kāi)圖，圓點(diǎn)為該面的頂ABD1342C86597最優(yōu)排序二把這 A 、 B 、 C 、 D 四個(gè)面各自劃分成 n2 個(gè)單位三角形, 并把 14n2 分別填入四個(gè)面總共 4n2個(gè)三角形中

38、。現(xiàn)在要求你編程求由三角形組成的最大排序二。三角形，可選它三個(gè)相鄰 ( 有公共對(duì)于任一邊的三角形相鄰 ) 的三角形中任意一個(gè)作為父結(jié)點(diǎn)，其余兩個(gè)分別作為和右孩子。當(dāng)然，做根結(jié)點(diǎn)的三角形不需要父結(jié)點(diǎn)，而左孩子和右孩子對(duì)于二是都必須的。中的任意結(jié)點(diǎn)來(lái)說(shuō)并不最優(yōu)排序二舉例 給出四面上的數(shù)如下圖 則最優(yōu)排序二如右圖A 面B 面C 面D 面分析設(shè) di, j, k 為根是 i,結(jié)點(diǎn)范圍為 jk 時(shí)的最大排序二結(jié)點(diǎn)個(gè)數(shù)i 有三個(gè)鄰居可以作 i 的子樹(shù)的根 ,但不在j,k 范圍內(nèi)的結(jié)點(diǎn)是不能選的 . 考慮 i 所有能選的鄰居 u, 根據(jù)u 和i 的唯一確狀態(tài)轉(zhuǎn)移時(shí)定它是i 的左子樹(shù)還是右子樹(shù) ., 取左子樹(shù)

39、和右子樹(shù)各自的最大值并相加即可結(jié)點(diǎn)范圍的設(shè)立自然的排除了把父親選作兒子的情況 ,也避免了兩棵子樹(shù)的交叉分析狀態(tài)有三維 ,似乎是 O(n6) 的,但其中一維i 的父親取決于 i 的父親 ,因此只需要是它的第幾個(gè)鄰居狀態(tài)數(shù)是 O(n2) 的( 狀態(tài)轉(zhuǎn)移時(shí)間 O(n2), 是 O(n4) 的三角形有 4n2 個(gè) ),總時(shí)間 O(n4).空間也提示:用記憶化搜索來(lái)實(shí)現(xiàn)本題的動(dòng)態(tài)規(guī)劃可以大大降低編程復(fù)雜度Bugs 公司Bugs 公司生產(chǎn)一種 2×3的高科技嵌入 N×M （ N150,M10 ）的模板內(nèi)，損壞的小已被標(biāo)上黑色記號(hào)NNM內(nèi)不能有黑色記號(hào)，同時(shí)與不能重疊。將盡量多的嵌入模板

40、M分析M<=10,可以考慮信息壓縮的動(dòng)態(tài)定義基線(xiàn) Bi,j 為前 i-1 列和第 i 列前j 行組成的圖形 ,若從右往左從下往上處理 ,則Bi,j 為考慮格子 (i,j) 時(shí)的剩余棋盤(pán)分析剩余棋盤(pán) Bi,j 上能切下多少Bi,j 已經(jīng)有哪些格子被占用了用 (0,2,1,0,2) 表示每行已經(jīng)被占了幾個(gè)格要取決于子( 注意 :能用)如果占了左邊的格子 ,右邊也不分析把占用情況看成 3 進(jìn)制數(shù),則有 3M 種情況設(shè) di,j,P 為 Bi,j 的占用情況為 P 時(shí)最多能數(shù),轉(zhuǎn)移方式 :忽略 ;放 2*3;嵌入的放 3*2.下圖為處理到深灰色格時(shí)選擇放置 3*2分析狀態(tài)有 MN3M 個(gè),轉(zhuǎn)移為

41、 O(1) 的,總時(shí)間復(fù)雜度為 O(MN3M)空間復(fù)雜度為 O(MN3M),但可以用滾動(dòng)數(shù)組優(yōu)化,即只保存相鄰三列的占用情況，降為 O(M3M) ，可以承受優(yōu)化:很多P 是不可能出現(xiàn)的 ,因?yàn)橹挥?*3 和 3*2 兩種占用,無(wú)法產(chǎn)生單獨(dú)的一列迷宮統(tǒng)計(jì)Jimmy辦了一個(gè)游園活動(dòng)，其中一個(gè)項(xiàng)目是讓游客去走一個(gè)隨機(jī)生成的 m 行 n 列(1m5,1n6) 的迷宮，迷宮里有空地，也有物（每個(gè)物恰好占一個(gè)）。游客總是從左上角走到右下角，每次可以往東南西北四個(gè)方向之一行走迷宮的生成方式很簡(jiǎn)單：每一個(gè)格子都有一個(gè)獨(dú)立的概率 p ，表示該格子為物的概率。如果程序生成了一個(gè)無(wú)解的迷宮，它會(huì)重新生成一個(gè)。你的任

42、務(wù)是計(jì)算每個(gè)格子成為一個(gè)有解迷宮中的物的概率。分析m 和n 都很小,是否可以隨便做呢 ? m=n=5 時(shí)有解迷宮有 1,225,194 個(gè) m=5, n=6 時(shí)高達(dá) 30,754,544 個(gè)如果把所有有解迷宮都列舉出來(lái)再計(jì)算概率，需要花費(fèi)約 10 分鐘的時(shí)間。思路：不列舉所有有解迷宮，而是把這些迷宮分成若干個(gè)不相交的集合，在每個(gè)集合中分別計(jì)算概率分析一樣 ,考慮像經(jīng)典的信息壓縮動(dòng)態(tài)列一列遞推一需要知道當(dāng)前列（或者多列）的哪些信息 ?的信息 ,如果只是簡(jiǎn)單的保存是否有保存一列、兩列或者三列都可能不夠。如果全部保存完，就沒(méi)有意義了。怎么辦呢？分析只當(dāng)前列的每個(gè)格子是否能和起點(diǎn)連通也是不對(duì)的，因此即

43、使當(dāng)前某個(gè)格子和起點(diǎn)不連通， 以后也是可能連通的。這樣做在狀態(tài)轉(zhuǎn)移的時(shí)候遇到了當(dāng)前列 y 中每?jī)蓚€(gè)格子是否連正確的做法是通方法一：每?jī)蓚€(gè)格子用 01 表示，一共 m2/2 個(gè)格子對(duì)，共 2m*m/2方法二：種狀態(tài)，太大每個(gè)格子 (x,y) 的 Px 值， 0 表示它和起點(diǎn)連通，否則它表示同列中與該格連通的所有格子的最小行編號(hào)（如果沒(méi)有這樣的格子，則 Px = x ）。這樣狀態(tài)最多 (m+1)! 個(gè)，可以承受分析用 S(i, P) 表示共 i 列，最后一列的連通情況為P 的所有迷宮集合為了統(tǒng)計(jì)和各個(gè)格子相關(guān)的概率，需要增加一維 b ，用 di, P, b 表示 S(I, P) 中最后一列第 b

44、個(gè)格子為的迷宮總概率 ,為了方便 b=0 表示總概率b 的選擇有 mn+1 種, P 的元素有 (m+1)! 個(gè)分析這樣，每次進(jìn)行狀態(tài)轉(zhuǎn)移時(shí)，枚舉當(dāng)前列的所有 (m+1)!(mn+1) 種狀態(tài)和 2m 種決策（下一列的情況），狀態(tài)轉(zhuǎn)移的時(shí)候需要做 BFS ，但是由于只需要用上一列的P 值和新列，因此 BFS 時(shí)間 2m+1當(dāng) i 、 P 和決策一定時(shí)只需要 BFS 一次即可計(jì)算出新的 P ，因此對(duì)于所有 b, di, P, b 的總時(shí)間為2m(2m+1+mn+1)=O(2mmn)計(jì)算分析(i,P) 狀態(tài)有 n*(m+1)! 個(gè)，因此總時(shí)間為n(m+1)!*O(2mmn) = O(mn22mm!

45、) 。顯然和 m 有比 n 大得多，因此總認(rèn)為當(dāng)m 大于 n 時(shí)交換 m,n ，并把矩陣翻轉(zhuǎn)?？梢杂脻L動(dòng)數(shù)組，空間是 O(m+1)!mn) 的貪吃的九有N 個(gè)果子的果樹(shù)，每個(gè)樹(shù)枝都有一個(gè)難受值把果子分成 M 份，每份給一個(gè)頭吃。每個(gè)頭至少吃一個(gè)果子，大頭必須吃果子 1 ，且一共吃 K 個(gè)同一個(gè)頭吃的果子如果有樹(shù)枝相連，增加難受值。讓總難受值盡量小最大的果子1320441510512(a)(b)大頭吃 4 個(gè)果子，用實(shí)心點(diǎn)標(biāo)識(shí)；小頭吃 4 個(gè)果子，用空心點(diǎn)標(biāo)識(shí)；九的難受值為 4，因?yàn)閳D中用細(xì)邊標(biāo)記的樹(shù)枝被大頭了。分析如果果子不夠吃（即 N<K+M-1 ），那么肯定無(wú)解；否則，至少存在一組解

46、 M 2 ，如果一段樹(shù)枝兩邊的果子都是大頭吃或都不是大頭吃，那么這段樹(shù)枝就要被； M3 ，小頭至少有兩個(gè)。在確定大頭吃的果子以后， 把剩下的果子按照在整棵樹(shù)上高度的奇偶性分成兩類(lèi)，讓第一個(gè)小頭吃高度為奇數(shù)的果子，第二個(gè)小頭吃高度為偶數(shù)的果子，則連接這些果子的樹(shù)枝都不需要。顯然，這樣的分配情況是最優(yōu)的因此，可以只考慮大頭分析d(i,j,k) 表示以點(diǎn) i 為根的子樹(shù)中有 j 個(gè)果子分給大頭的最小難受值， k 0 表示點(diǎn) i 給小頭吃， k=1 表示點(diǎn) i 給大頭吃狀態(tài)轉(zhuǎn)移的時(shí)候，需要枚舉 i 的每個(gè)子結(jié)點(diǎn)所在的子樹(shù)分配幾個(gè)果子給大頭吃，以及這些子結(jié)點(diǎn)是否由大頭吃，情況很復(fù)雜， 應(yīng)當(dāng)怎樣處理呢？分

47、析問(wèn)題的復(fù)雜之處在于 i 可能有多個(gè)兒子需要考慮，但是由于所有兒子形成一個(gè)線(xiàn)性結(jié)構(gòu)，可以在這個(gè)線(xiàn)性結(jié)構(gòu)中再次使用動(dòng)態(tài)）?；蛘?，把這個(gè)二次動(dòng)態(tài)（第二層動(dòng)態(tài)的過(guò)程理解成把多轉(zhuǎn)化為二也可以。狀態(tài)變化： d(i,j,k) 表示以點(diǎn) i 為根的子樹(shù)和以它右邊的兄弟為根的子樹(shù)中有 j 個(gè)果子分給大頭的最小難受值， k 0 表示點(diǎn) i 的父結(jié)點(diǎn)給小頭吃， k 1 表示點(diǎn) i 的父結(jié)點(diǎn)給大頭吃分析狀態(tài)量為 NK ，每次需要枚舉給左兒子和右兄弟分配的果子數(shù)，因此決策量為 O(K) ， 總 O(NK2)設(shè) C(i) 為i 的子樹(shù)和右兄弟們的子樹(shù)的總結(jié)點(diǎn)數(shù)，則 j>C(i) 時(shí)狀態(tài) di,j 沒(méi)有意義 鏈的情

48、形：不需要枚舉決策 完全二：合法狀態(tài)只有 O(N) 個(gè)的蜜月賓館有一間蜜月房非常舒適 ,經(jīng)理在每年年底都會(huì)收到第二年的所有蜜月房預(yù)訂單。第 i 中預(yù)訂單包括：到達(dá)日期 Si 、離去日期 Ti 和費(fèi)用 Ci不與任何其他預(yù)訂要求發(fā)生的預(yù)訂單必然會(huì)被接受 ; 對(duì)于其他訂單 ,疊任兩份的時(shí)間都不能重你的任務(wù)是在所有合法方案中找出獲利第k(k<=100) 大的方案 .當(dāng)然，可能有若干種方案3 種方案的收入同時(shí)的獲利是一樣大的。假為 3 ，有 2 種方案的收入為 2 ，則收入為 3 的方案都屬于獲利最大，收入為 2 的方案都屬于獲利第二大。所有的住、離店登記都在中午 12 點(diǎn)進(jìn)行。共有 r分析首先考慮 k=1 的情況 .由于天數(shù)比較小( 最多 366 天 ), 因此設(shè) di 為前i 天可到達(dá), Si 為右端點(diǎn)在i 的線(xiàn)段集 .的最大兩類(lèi)轉(zhuǎn)移 不選取 Si有的任何線(xiàn)段 ,為 di-1為w 的線(xiàn)段 , 選取