《算法藝術與信息學競賽》45道動態(tài)規(guī)劃題目

1、算法藝術與信息學競賽45道動態(tài)規(guī)劃題目索引 【POJ1141】括號序列 【POJ1191】棋盤分割 【SPOJ196】決斗 【AOA】跳舞機 【AOA】積木游戲 【AOA】藝術館的火災 【AOA】機器人的名字 【UVa10559】方塊消除索引 【AOA】公路巡邏 【POJ1074】并行期望值 【AOA】高性能計算機 【AOA】模板匹配 【AOA】不可解碼的編碼 【AOA】青蛙的煩惱 【AOA】排列問題 【AOA】最優(yōu)排序二叉樹索引 【POJ1038】 Bugs公司 【UVa10531】迷宮統(tǒng)計 【AOA】貪吃的九頭龍 【AOA】快樂的蜜月 【AOA】移動機器人 【UVa10271】佳佳的筷子

2、【AOA】偷懶的工人 【AOA】鐵路調度索引 【POJ1691】平板涂色 【POJ1947】道路重建 【ZJUxxx】圓和多邊形 【AOA】鐵球落地 【UVA10118】免費糖果 【AOA】丟三落四的老鼠 【AOA】最長公共子序列問題 【UVA10635】排列的LCS問題索引 【UVAxxx】最長上升子序列問題 【UVAxxx】最優(yōu)二分檢索樹問題 【POJ1180】任務調度問題 【AOA】序列分割問題 【AOA】多排列的LCS 【POJ1159】回文詞 【AOA】友好城市 【POJ1160】郵局索引 【AOA】基因串 【POJ1946】奶牛轉圈 【AOA】元件折疊 【AOA】 DNA序列 【A

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

4、k=j-1) 狀態(tài)O(n2), 轉移O(n), 共(n3)棋盤分割 將一個88的棋盤進行如圖所示的分割：將原棋盤割下一塊矩形棋盤并使剩下部分也是矩形，再將剩下的部分繼續(xù)如此分割，這樣割了(n-1)次后，連同最后剩下的矩形棋盤共有n（n15）塊矩形棋盤（每次切割都只能沿著棋盤格子的邊進行）。棋盤分割 原棋盤上每一格有一個分值，一塊矩形棋盤的總分為其所含各格分值之和?，F在需要把棋盤按上述規(guī)則分割成n塊矩形棋盤，并使各矩形棋盤總分的均方差均方差最小。 (a) 允許的分割方案 (b) 不允許的分割方案 分析 變形均方差公式 平均值是一定的（等于所有方格里的數的和除以n） 只需要讓每個矩形總分的平方和盡

5、量小21211222)(1)2)(1xxnxxxxnnniiniinii分析 考慮左上角坐標為(x1,y1)，右下角坐標為(x2,y2)的棋盤，設它把切割k次以后得到的k+1塊矩形的總分平方和最小值為dk,x1,y1,x2,y2 狀態(tài)轉移: 沿著某某橫線切或者豎線切，然后選一塊選一塊繼續(xù)切, 如橫著切的兩類決策是 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 設m為棋盤邊長，則狀態(tài)數目為m4n，決策數目為O(m) 轉移時間取決于計算sx1,y1,x2,y2的時間

6、預處理先用O(m2)時間算出左上角為(1,1)的所有矩陣元素和，這樣狀態(tài)轉移時間就是O(1)，總的時間復雜度為O(m5n) 決斗 編號為1n的n個人按逆時針方向排成一圈圈，他們要決斗n-1場。每場比賽在某相鄰兩人間進行，敗者退出圈子，緊靠敗者右邊的人成為與勝者直接相鄰的人。 任意兩人之間決斗的勝負都將在一矩陣中給出（如果Ai,j=1則i與j決斗i總是贏，如果Ai,j=0則i與j決斗時i總是輸）， 求出所有可能可能贏得整場決斗的人的序號分析 di,j表示是否有可能i和j相遇, 則第i個人能取得最后的勝利當且僅當di,i為true 狀態(tài)轉移: 考慮相遇前的最后一步, 則dI,j為true當且僅當

7、能找到一個k, 使得i能遇k, k能遇到j, 且 i或者j能打敗k 狀態(tài)有O(n2)個, 轉移有O(n)個, 共O(n3)跳舞機 DDR的主要內容是用腳來踩踏板。踏板有4個方向的箭頭，用1，2，3，4來代表 每首歌曲有一個箭頭序列，游戲者必須按照這個序列依次用某一只腳踩相應的踏板。在任何時候，兩只腳都不能在同一個踏板上，但可以同時待在中心位置0。 跳舞機 每一個時刻，必須移動而且只能移動一只腳去踩相應的箭頭，另一只腳不許移動。 跳DDR會消耗體力。從中心移動到任何一個箭頭耗費2單位體力，從任何一個箭頭移動到相鄰箭頭耗費3單位體力，移動到相對的箭頭（1和3相對，2和4相對）耗費4單位體力，而留在

8、原地再踩一下只需要1單位。 給定一首舞曲, 每個箭頭應該用哪只腳踩才能使體力消耗最少呢？例如對于序列LLUR, 用LLRR腳去踩，總的體力耗費為2 + 1 + 2 + 3 = 8單位分析 目前左腳在位置x, 右腳在位置y, 從第k個箭頭開始跳, 最少體力耗費為dx,y,k, 則 用左腳, dak, y, k+1 + effort(x, ak) 用右腳, dx, ak, k+1 + effort(y, ak) 狀態(tài)是O(n)的，決策是O(1)的, 總時間復雜度為O(n)積木游戲 有N塊編號依次為1，2，N的長方體積木。每塊積木有三條不同邊分別稱為a、b、c邊 從積木中選出若干塊分成M堆, 每堆至

9、少有1塊積木，并且第K堆中任意一塊積木的編號要大于第K+1堆中任意一塊積木的編號 b a c 積木游戲 每一堆積木要垂直摞成一根柱子,并滿足 除最頂上的一塊積木外，任意一塊積木的上表面同且僅同另一塊積木的下表面接觸，并且要求下面積木的上表面能包含上面的積木的下表面，也就是說，要求下面積木的上表面兩對邊的長度分別大于等于上面積木兩對邊的長度。 對于任意兩塊上下表面相接觸的積木，下面積木的編號要小于上面積木的編號 要求每堆積木的高度和盡量大 分析 我們從最后一堆積木開始, 一個個積木考慮 記di,a,b,k為已經用了前a個積木得到了i根柱子, 目前頂面為積木b的第k個面, 以后還能獲得的最大高度,

10、 有三類決策 新起一堆, di+1,a+1,a+1,k, 當im時合法 加在當前堆, di,a+1,a+1,k, 當放得上時合法 丟棄當前塊, di,a+1,b,k, 隨時合法 狀態(tài)O(n2m)個, 決策O(1), 總時間O(n2m)藝術館的火災 藝術館著火了. 這是一幢兩層的小樓，每層有N個房間，用兩個數分別表示藝術品價值和火勢. 滅火器最多只能發(fā)射K次，每次發(fā)射將覆蓋一個矩形的區(qū)域（矩形的高度可以是1也可以是2），所到之處不但火焰會被撲滅，藝術品也被摧毀。 你需要決定滅火器每次應該怎樣發(fā)射，才能將這次火災的損失降到最低限度。損失等于摧毀的藝術品總價值加上剩余的火勢總值40/50 50/40

11、 30/50 60/70 30/40 30/50 40/20 20/30 分析 模型：在一個2N的矩陣中，找出K個子矩陣。矩陣的每個元素有兩個值V和F。題目要讓K個子矩陣的V值和其他矩陣的F值之和最小，而如果我們令W=V-F，則目標轉換為讓K個子矩陣元素的W值之和最小 矩陣可以重疊，這給解題帶來不便。我們可以不考慮重疊情況，如圖所示1-43 重疊情況轉化為不重疊情況L R S(1,2,2,4) S(1,3,1,6)L R S(1,2,2,4) S(1,5,1,6)分析 用區(qū)域(i,j)來表示“第一行第i個格子右邊所有元素加上第二行第j個格子右邊的所有元素”這個區(qū)域，用ds,i,j來表示在這個區(qū)

12、域中選擇s個子矩陣，它們的元素總和的最小值 狀態(tài)轉移的決策是新矩形的放置, 有三類 第一行第i個格子不用, ds,i+1,j 在第一行從第i個格子開始放矩形, 設長度為L, 轉移到ds-1,i+L,j i=j時還可放置寬度為2的矩形, 轉移到ds-1, i+L, j+L 狀態(tài)O(kn2)個, 決策O(n), 轉移時間O(1)(先預處理), 總時間O(kn3)機器人的名字 考慮一種基于重復子串的壓縮方法 用Stk表示k個相同的子串St(其中St稱為重復子串，k是一個單字節(jié)整數，只占一個字符位置) 如果這k個子串并沒有連在一起，則可以在Stk的后面加上S1t1S2 t2Sr tr（1tik，tit

13、i+1），表示在第ti個St的后面放置Si，Si稱為插入子串 St和Si也都可以是壓縮后的字符串 比如I_am_WhatWhat_is_WhatWhat的壓縮結果為I_am_What4_is_2，長度為19 (例子中的空格用下劃線“_”表示，數字2和4實際上是用單字節(jié)二進制表示的) 名字不會以空格開始或結尾，大小寫敏感分析 令da,b表示以a, b為起止位置的串(記為Sa,b)的最短壓縮長度, 則目標為d1,L 狀態(tài)轉移 連接: da,b = minda,i + di+1,b, a=ib 壓縮: 需要確定重復子串. 當重復子串很多時, 決策枚舉的代價較大 壓縮決策可以通過動態(tài)規(guī)劃來枚舉!分析

14、ga,b,c表示將串Sa,b, 選擇長度為c的重復子串進行壓縮得到的最短長度. 枚舉插入串(可能為空)的下一個位置i, 狀態(tài)轉移方程為caiicadcbigcaicbigcbagciiScaaScbica3 1,min,1,1,1分析 邊界條件 da,b的狀態(tài)轉移方程 如何較快的判斷是否有Sa, a+c-1=Si, i+c-1? 從c=1開始遞推, 總O(L3)13, 1 1,121,abcbadbcbScaaSabcabcbag或者11min , 1, , minmin , , a i bi b ad a id ibd a bg a b i 分析 時間: 預處理O(L3), 核心O(L4),

15、 共O(L4) 空間 g: 本來是三維的O(L3)的, 但注意到在每個式子里b參量沒有發(fā)生變化, 故以b為階段遞推, 只需要O(L2)的空間 預處理結果: 如果用ha,b,c表示是否有Sa, a+c-1=Sb, b+c-1, 則又是三維的. 可以用鏈式存儲, 用nexta,b表示子串Sa,b的下一個相同子串的開始位置, 則只需要O(L2)的空間方塊消除 n個帶顏色方格排成一列，相同顏色的方塊連成一個區(qū)域（如果兩個相鄰方塊顏色相同，則這兩個方塊屬于同一區(qū)域） 游戲時，你可以任選一個區(qū)域消去。設這個區(qū)域包含的方塊數為x，則將得到x2分 方塊消去之后將產生空列, 此時其右邊的所有方塊就會向左移, 直

16、到所有方格連在一起方塊消除 下面是一個游戲的例子分析 輸入表示成兩個長度為L的數組color和len L表示有多少“段”不同的顏色方塊 colori表示第i段的顏色 leni表示第i段的方塊長度 題目的例子成color=1,2,3,1, len=1,4,3,1 用(i,j,k)表示在第ij段方塊的右邊添加k個顏色為colorj的方塊后得到的方塊序列, 相當于考慮第ij段, 但讓lenj的值增加k分析 d i,j,k表示把序列(i,j,k)消除的最大得分 考慮最后一段，有兩類決策 如果馬上消掉，就是di,j-1,0+(lenj+k)2； 如果和前面的若干段一起消，設這“若干段”中最后面的那一段是

17、p(i=pj)，得分為di,p,k+lenj+dp+1,j-1,0, 其中colorp=colorj 邊界條件是f i,i-1,0=0 時間O(n4), 建議用記憶化遞歸實現 公路巡邏 在一條沒有分岔的公路上有n（n50）個關口，相鄰兩關口之間的距離是10km。所有車輛在公路上的最低速度為60km/h，最高速度為120km/h，且只能在關口處改變速度。 有m(m300)輛巡邏車分別在時刻Ti從第ni個關口出發(fā)，勻速行駛到達第ni+1個關口，路上耗費時間為ti(s)。兩輛車相遇指他們之間發(fā)生超車現象或同時到達某個關口。 求一輛于6點整從第1個關口出發(fā)去第n個關口的車最少會與多少輛巡邏車相遇，以及

18、在此情況下到達第n個關口的最早時刻。所有車輛到達關口的時刻必須是整秒。 分析 di,T表示在時刻T到達第i個關口的途中與巡邏車最少相遇次數，狀態(tài)轉移方程為 函數wi-1,T-t,T是目標車于時刻T-t從第i-1個關口出發(fā)，于時刻T到達第i個關口途中與巡邏車相遇的次數 設每兩個關口間行駛時間有k種選擇, 狀態(tài)總數為O(kn2)，決策數目為O(k)，轉移時間依賴于w, 1, 1min,600300TtTiwtTidTidt分析 方法一：方法一：在每個決策中都進行一次計算，對所有從第i個關口出發(fā)的巡邏車進行判斷，由于每輛巡邏車恰好被判斷一次，故這樣每個狀態(tài)的計算w的平均時間復雜度為O(m/n)，算法

19、總時間復雜度為O(kn2)O(k)O(m/n)=O(k2nm)。 方法二：方法二：仔細觀察狀態(tài)轉移方程可以發(fā)現，在對狀態(tài)di,T進行轉移時，所計算的函數w都是從第i個關口出發(fā)的，而且出發(fā)時刻都是T，只是相應的到達時刻不同。能否考慮這些車之間的聯(lián)系，從而利用已經得出的結果，減少重復運算呢？ 分析 令gk=wi,T,k+1-wi,T,k, 設到達時間為k和k+1的目標車分別為車A和車B 對于每輛從第i個關口出發(fā)的巡邏車C，設其出發(fā)和到達時刻分別為St和Tt，則 Ttk+1，車A車B與車C的相遇情況相同 Tt=k，則車A與車C相遇，車B的分析又分為，若St=T，則車B不與車C相遇，否則車B也與車C相

20、遇 Tt=k+1,則車B與車C相遇，對車A的分析又分為，若St=T，則車A不與車C相遇，否則車A也與車C相遇分析 綜合起來 gk=G(Tt=k+1)&(St=T)G(Tt=k)& (St=T) G(P)表示所有從關口i出發(fā)且滿足條件P的巡邏車數目 計算di,T時 先對所有從第i個關口出發(fā)的巡邏車進行一次掃描, 求出wi,T,T+300的同時求出gT+301.T+600，時間復雜度為O(m/n) 以后的轉移中，由wi,T,k+1=wi,T,k+gk，僅需O(1)時間就可以求出函數值w，狀態(tài)轉移時間僅為O(1) 總時間O(kn2)*(O(m/n)+k*O(1)=O(knm+k2n2) 由于n50,

21、 m300，方法二比方法一快得多并行期望值 考慮一個可以并行執(zhí)行兩個高級語言程序的機器。高級語言程序由若干條賦值指令組成，形式是： := op 變量名由不超過20個字母組成。運算數是變量名或小于100的正整數。op是運算符，可以是加號“+”或者減號“-” 執(zhí)行前, 程序被翻譯成機器語言。X := Y + Z翻譯成Mov R1, YMov R2, ZAdd R1, R2Mov X, R1 Mov指令把第二個操作數送到第一個中去，Add操作進行加法，并把結果保存在第一個操作數中。注意Y和Z代表變量或者整數常量。X := Y - Z 的機器語言代碼類似并行期望值 處理器接受了兩個機器語言程序后，每次

22、隨機選一個程序，執(zhí)行它的下一條指令。如果某個程序執(zhí)行完畢，處理器會連續(xù)把另一個程序執(zhí)行完。兩個程序共享所有變量（一開始的時候各個變量的值均為0），但擁有兩個獨立的寄存器R1和R2 由于執(zhí)行順序不確定，最后各個變量的值也是不確定的。不過，可以計算出每個變量在所有情況下最終值的平均數（即并行期望值）?，F在給你兩個高級語言程序，請編程算出所有變量的并行期望值。每個高級語言程序最多有25條指令，兩個程序最多共使用10個變量。 分析 首先把高級語言程序翻譯成機器語言, 翻譯規(guī)則 := + := + := op := + 其中x是程序代號. 即一共有四個寄存器: R11, R12, R21, R22, 和

23、普通變量同等對待 dx,y,k表示程序1執(zhí)行完x條指令, 程序2執(zhí)行完y條指令后變量k的并行期望值分析 情況一: 剛剛執(zhí)行完第1個程序的第x條指令 該指令不是在給k賦值, 等于dx-1,y,k 指令形如:= op , 等于dx-1,y,a op dx-1,y,b 記這個結果為K1 情況二: 剛剛執(zhí)行完的是第2個程序的第y條指令, 按同樣的方法可計算出K2 情況一的概率是x/(x+y), 情況二是y/(x+y) 按期望公式, dx,y,k=(x*K1+y*K2)/(x+y)分析 為什么在情況一的賦值語句后, k的期望等于dx-1,y,a op dx-1,y,b? 期望的線性性質 為什么情況一的概

24、率是x/(x+y), 情況二是y/(x+y)? 狀態(tài)(x-1, y)和(x, y-1)的概率比為到達兩個狀態(tài)的路徑條數比, 即 C(x+y-1,x-1)/C(x+y-1,y-1), 展開得 (x+y-1)!/(x-1)!y!/(x+y-1)!/x!(y-1)!=x/y高性能計算機 一個大型計算任務可以劃分成很多A類任務和B類任務. 所有A類任務都相同, 所有B類任務都相同. 所有任務的相對執(zhí)行順序沒有要求 有p個計算結點, 對于第i個結點 三種工作狀態(tài)：待機、A類和B類。初始為待機狀態(tài)，從其他的狀態(tài)轉入A或B狀態(tài)分別需要tiA和tiB的時間 連續(xù)處理x個A類子任務，時間為t = kiAx2；類

25、似定義kiB 你需要進行任務分配, 即給每個結點設置任務隊列. 隊列中一串連續(xù)的同類子任務不能被分成兩部分執(zhí)行。所有結點都同時開始運行，目標是最后結束計算的結點的完成時間盡可能早分析 該問題可以分成兩個子問題： 計算第i個結點完成ai個A任務和bi個B任務的最短時間 給第i個結點分配ai個A任務和bi個B任務，取所有結點運行時間的最大值 問題1的解決: 讓di,t,a,b表示結點i，還有a種A任務和b種B任務，并且當前需要執(zhí)行t類任務（t=A或B）所需要的最短時間分析 決策為當前執(zhí)行j個連續(xù)序列, di,A,a,b=mindi,B,a-j,b+tiA+kiA*j2 問題1的解fi,a,b=mi

26、ndi,A,a,b, di,B,a,b 問題2是任務分配問題. gi,a,b代表前i個結點完成a個A任務b個B任務的最短時間，決策為給任務i分配j個A任務和k個B任務, 即gI,a,b=min maxdi-1,a-j,b-k, fi,j,k 時間O(pna2nb2), 空間O(nanb), 如何優(yōu)化?模板匹配 *代表零個或多個字符。通配符Q稱兩個通配符P1和P2的公共模板，如果被Q匹配的字符串一定同時被二者匹配。如ba*ab是*ab*和ba*b的公共模板 P1、P2的一個模板集合Q1，Q2，Qn稱為完備的，如果每個Qi都是P1、P2的公共模板，且任何一個既能被P1匹配又能被P2匹配的字符串至少

27、能被一個Qi匹配 給出P1，P2，求模板數目最少的完備模板集合 例如，對于ba*ab和*ab*，一個包含最少數目模板的完備集合為：ba*ab*b, bab*b, ba*ab, bab 分析 如果把一個模板看作一個集合（即它能匹配到所有字符串集合），則模板包含關系等同于集合包含關系 本題的任務是求P1和P2的交集的最小覆蓋(即這些集合的并為P1和P2的交, 且集合數目應盡量小) 基本思想: 枚舉每一個種同時被兩個模板匹配的串s，對每種情況都構造一個模板去覆蓋它分析 令子問題(i,j)表示需要匹配P1從第i位起的剩下串和P2從第j位起的剩下串，狀態(tài)轉移有四種情況： a*和b*沒有交集，因為無論公共

28、串s的第一位是什么都不行。 a*b和ab*有交集，且公共串s的第一位只有一種情況：a，剩下的任務是要讓s從第2位起同時匹配*b和b*。轉移到(i+1,j+1)。 a*b和*ab有交集，且s的第一位必須是a。顯然對于P1來說還需要匹配*b，但是對于P2來說，可以匹配ab，也可以匹配*ab，甚至可以匹配b。則(i,j)轉化為了(i+1,j)、(i+1,j+1)和(i+1,j+2) *ab和*b有交集，且s的第一位隨便是什么都可以，用*表示（想一想，為什么）?，F在狀態(tài)轉移到了什么地方呢？是(i+1,j)和(i,j+1) 好象有點亂. 仔細分析后兩種情況, *可以看為空或者吃掉一個字符不可解碼的編碼

29、給定n(n20)個01編碼串S1,S2,Sn，尋找一個編碼串T，至少可被分解為兩種不同的Si的排列 例如：給定5個01編碼串：S1=0110，S2=00，S3=111，S4=001100，S5=110。一個符合要求的編碼串T是：001100110，兩種分解方法為 00+110+0110 (S2+S5+S1) 001100+110 (S4+S5) 而只有一種分解方法 0110+110 (S1+S5) 尋找長度最短的符合要求的編碼串T，若有多個符合要求的最短編碼串T，則輸出字典順序最小的分析 先考慮搜索策略。搜索的關鍵是編碼串T至少存在兩種不同的分解方法。從搜索分解方法出發(fā)，同時搜索兩種分解方法，

30、可以大大減少搜索量。分析 不完整的分解方案所無法匹配的剩余部分，一定是某個S編碼串的后綴。 定義狀態(tài)di,j為：當B部分為第i個數字串從第j+1開始的后綴時，A部分部分的最短長度 邊界: 當存在某個長度為j的串為串i的前綴時di,j=j, 其他di,j為無窮大 A B 分析 轉移和A無關, 只考慮B. 從某個狀態(tài)di,j出發(fā)進行轉移，可以分為兩種情況： 某串k是B的前綴，則用di,j+Lk更新di,j+Lk B是某串k的前綴, 則用di,j+Li-j更新dk,Li-j 最后的解是所有dk,Lk 中最小的一個分析 因為題目要求找出的串是長度最短且在同長度的串中字典序最小的一個，因此，若長度不等時

31、，可以直接取小的那個；若長度相等，則要追溯前面的狀態(tài)，取字典序較小的那個。這與一般的動態(tài)規(guī)劃是不太相同的，需要特別注意 為了編程方便，可以采用記憶化搜索的方式。另外，由于程序中需要大量用到查找某個字符串是否存在的操作，為了提高程序效率，可以用Trie的結構來存儲青蛙的煩惱 池塘里有n片荷葉（1n1 000），它們正好形成一個凸多邊形。按照順時針方向將這n片荷葉順次編號為1，2，n。 有一只小青蛙站在1號荷葉上，它想跳過每片荷葉一次且僅一次（它可以從所站的荷葉跳到另外任意一片荷葉上）。同時，它又希望跳過的總距離最短。 請你編程幫助小青蛙設計一條路線。 分析 最短的路線中不存在相交的邊。證明: 路

32、線變換（實線表示一步到達，虛線多步） 根據這個結論可以知道：從1出發(fā)第一步只能到2或者n。如果第一步到了2，則第二步只能到n或者3 ，因為邊不能相交！ 1 A 1 A B C C B 分析 任意時刻沒有經過的頂點構成區(qū)間 設ds,L,0表示從s出發(fā)，遍歷ss+L-1中的頂點一次且僅一次的最短距離； ds,L,1表示從s+L-1出發(fā)，遍歷ss+L-1中的頂點一次且僅一次的最短距離。 容易寫出狀態(tài)轉移方程, 時空均為O(n2)排列問題 在整數1，2，N的排列中，有些排列滿足性質A：該排列中除了最后一個整數以外的每一個整數后面都跟有（不必直接緊跟）一個同它相差為1的整數。例如：N = 4，排列143

33、2是具有性質A的，而2431則不滿足。 設有一個N個數的排列，已知其中P(PN)個位置上的數，求共有多少個這樣的排列在P個位置上具有已知的數，且具有上述性質A。例如：N = 4，且已知第1位、第2位分別是1和4，則1432，1423就是這樣的兩個排列。 分析 通過枚舉N比較小的時候滿足題目的排列，發(fā)現一個規(guī)律：任何一個排列的后k位 （lkn）是若干連續(xù)整數組成的集合?？梢杂脭祵W歸納法證明這個結論 進一步地，還可以證明只要滿足任意后k位（lkn）是若干連續(xù)整數組成的集合，則這個排列一定符合題目要求。 下面給出時空復雜度均為O(n2)的算法 分析 設ds, r表示滿足下面條件的序列C的總數 為s,

34、 s+1s+r-1的一個排列 任意后k位都是連續(xù)整數組成的集合 如果原問題中倒數第i個位置上的數已經確定為x（lir），那么C的倒數第i個位置上的數也要是x。由加法原理得 ds,r= ds+1,r-1， 倒數第 r 位必須為 s ds,r-1， 倒數第 r 位必須為 s+r-1 ds,r-1+ds+1,r-1， 倒數第 r 位不確定 0 其他情況，不能保證后 r-1 位為連續(xù)整數，故無解 最優(yōu)排序二叉樹 邊長為3的正三角形分成三層共9個小的正三角形，把它們從頂到底，從左到右以19編號。邊長為n的正三角形可以劃分成n2個單位三角形。 四個這樣的邊長為n的正三角形可以組成一個三棱錐。將正三棱錐的三

35、個側面依順時針次序(從頂向底視角)編號為A, B, C，底面編號為D。右圖為展開圖，圓點為該面的頂 1 3 2 4 6 8 7 9 5 C D B A 最優(yōu)排序二叉樹 把這A、B、C、D四個面各自劃分成n2個單位三角形, 并把14n2分別填入四個面總共4n2個單位三角形中。 現在要求你編程求由單位三角形組成的最大排序二叉樹。 對于任一單位三角形，可選它三個相鄰(有公共邊的三角形相鄰)的單位三角形中任意一個作為父結點，其余兩個分別作為左孩子和右孩子。當然，做根結點的單位三角形不需要父結點，而左孩子和右孩子對于二叉樹中的任意結點來說并不是都必須的。 最優(yōu)排序二叉樹 舉例 給出四面上的數如下圖 則最

36、優(yōu)排序二叉樹如右圖 A 面 B 面 C 面 D 面 分析 設di, j, k為根是i, 結點范圍為jk時的最大排序二叉樹結點個數 i有三個鄰居可以作i的子樹的根, 但不在j,k范圍內的結點是不能選的. 考慮i所有能選的鄰居u, 根據u和i的關系可唯一確定它是i的左子樹還是右子樹. 狀態(tài)轉移時, 取左子樹和右子樹各自的最大值并相加即可 結點范圍的設立自然的排除了把父親選作兒子的情況, 也避免了兩棵子樹的交叉分析 狀態(tài)有三維, 似乎是O(n6)的, 但其中一維取決于i的父親, 因此只需要記錄i的父親是它的第幾個鄰居 狀態(tài)數是O(n2)的(單位三角形有4n2個), 狀態(tài)轉移時間O(n2), 總時間O

37、(n4). 空間也是O(n4)的 提示: 用記憶化搜索來實現本題的動態(tài)規(guī)劃可以大大降低編程復雜度 Bugs公司 Bugs公司生產一種23單位尺寸的高科技芯片嵌入NM（N150,M10）單位尺寸的模板內，損壞的單位小方格已被標上黑色記號 芯片內不能有黑色記號，同時芯片與芯片不能重疊。將盡量多的芯片嵌入模板 M M N N 分析 M=10, 可以考慮信息壓縮的動態(tài)規(guī)劃 定義基線Bi,j為前i-1列和第i列前j行組成的圖形, 若從右往左從下往上處理, 則Bi,j為考慮格子(i,j)時的剩余棋盤剩余棋盤分析 剩余棋盤Bi,j上能切下多少芯片要取決于Bi,j已經有哪些格子被占用了 用(0,2,1,0,2

38、)表示每行已經被占了幾個格子(注意: 如果占了左邊的格子, 右邊也不能用)分析 把占用情況看成3進制數, 則有3M種情況 設di,j,P為Bi,j的占用情況為P時最多能嵌入的芯片數, 轉移方式: 忽略; 放2*3; 放3*2. 下圖為處理到深灰色格時選擇放置3*2分析 狀態(tài)有MN3M個, 轉移為O(1)的, 總時間復雜度為O(MN3M) 空間復雜度為O(MN3M), 但可以用滾動數組優(yōu)化, 即只保存相鄰三列的占用情況，降為O(M3M)，可以承受 優(yōu)化: 很多P是不可能出現的, 因為只有2*3和3*2兩種芯片, 無法產生單獨的一列占用迷宮統(tǒng)計 Jimmy自己辦了一個游園活動，其中一個項目是讓游客

39、去走一個隨機生成的m行n列(1m5, 1n6)的迷宮，迷宮里有空地，也有障礙物（每個障礙物恰好占一個方格）。游客總是從左上角走到右下角，每次可以往東南西北四個方向之一行走 迷宮的生成方式很簡單：每一個格子都有一個獨立的概率p，表示該格子為障礙物的概率。如果程序生成了一個無解的迷宮，它會重新生成一個。 你的任務是計算每個格子成為一個有解迷宮中的障礙物的概率。 分析 m和n都很小, 是否可以隨便做呢? m=n=5時有解迷宮有1,225,194個 m=5, n=6時高達30,754,544個 如果把所有有解迷宮都列舉出來再計算概率，需要花費約10分鐘的時間。 思路：不列舉所有有解迷宮，而是把這些迷宮

40、分成若干個不相交的集合，在每個集合中分別計算概率分析 考慮像經典的信息壓縮動態(tài)規(guī)劃一樣, 一列一列遞推 需要知道當前列（或者多列）的哪些信息? 如果只是簡單的保存是否有障礙的信息, 保存一列、兩列或者三列都可能不夠。如果全部保存完，就沒有意義了。怎么辦呢？ 分析 只記錄當前列的每個格子是否能和起點連通也是不對的，因此即使當前某個格子和起點不連通，以后也是可能連通的。這樣做在狀態(tài)轉移的時候遇到了困難 正確的做法是記錄當前列y中每兩個格子每兩個格子是否連通 方法一：方法一：每兩個格子用01表示，一共m2/2個格子對，共2m*m/2種狀態(tài)，太大 方法二：方法二：記錄每個格子(x,y)的Px值，0表示

41、它和起點連通，否則它表示同列中與該格連通的所有格子的最小行編號（如果沒有這樣的格子，則Px = x）。這樣狀態(tài)最多(m+1)!個，可以承受分析 用S(i, P)表示共i列，最后一列的連通情況為P的所有迷宮集合 為了統(tǒng)計和各個格子相關的概率，需要增加一維b，用di, P, b表示S(I, P)中最后一列第b個格子為障礙的迷宮總概率, 為了方便b=0表示總概率 b的選擇有mn+1種, P的元素有(m+1)!個分析 這樣，每次進行狀態(tài)轉移時，枚舉當前列的所有(m+1)!(mn+1)種狀態(tài)和2m種決策（下一列的障礙情況），狀態(tài)轉移的時候需要做BFS，但是由于只需要用上一列的P值和新列，因此BFS時間2

42、m+1 當i、P和決策一定時只需要BFS一次即可計算出新的P，因此對于所有b, 計算di, P, b的總時間為2m(2m+1+mn+1)=O(2mmn)分析 (i,P)狀態(tài)有n*(m+1)!個，因此總時間為n(m+1)!*O(2mmn) = O(mn22mm!)。 顯然和m有關的項比n大得多，因此總認為當m大于n時交換m,n，并把矩陣翻轉。 可以用滾動數組，空間是O(m+1)!mn)的貪吃的九頭龍 有N個果子的果樹，每個樹枝都有一個難受值 把果子分成M份，每份給一個頭吃。每個頭至少吃一個果子，大頭必須吃果子1，且一共吃K個 同一個頭吃的果子如果有樹枝相連，增加難受值。讓總難受值盡量小 大頭吃

43、4 個果子，用實心點標識； 小頭吃 4 個果子，用空心點標識； 九頭龍的難受值為 4，因為圖中用細邊標記的樹枝被大頭吃掉了。 (a) (b) 最大的果子 20 4 13 15 5 12 10 20 13 4 5 15 10 12 分析 如果果子不夠吃（即NC(i)時狀態(tài)di,j沒有意義 鏈的情形：不需要枚舉決策 完全二叉樹：合法狀態(tài)只有O(N)個快樂的蜜月 賓館有一間蜜月房非常舒適, 經理在每年年底都會收到第二年的所有蜜月房預訂單。第i中預訂單包括：到達日期Si、離去日期Ti和費用Ci 不與任何其他預訂要求發(fā)生沖突的預訂單必然會被接受;對于其他訂單, 任兩份的時間都不能重疊 你的任務是在所有合

44、法方案中找出獲利第k(k=100)大的方案. 當然，可能有若干種方案的獲利是一樣大的。假如有3種方案的收入同時為3，有2種方案的收入為2，則收入為3的方案都屬于獲利最大，收入為2的方案都屬于獲利第二大。 所有的住、離店登記都在中午12點進行。共有r個預訂要求(r20,000)分析 首先考慮k=1的情況. 由于天數比較小(最多366天), 因此設di為前i天可到達的最大收益, Si為右端點在i的線段集. 有兩類轉移 不選取Si的任何線段, 為di-1 選取某條左端點為j, 權值為w的線段, 為dj+w 時間復雜度為O(D+r), 因為所有訂單恰好被考慮一次, 其中D為一年的天數分析 前i天收益前

45、k大的方案, 前j天(j i)天也是前k大的, 因此每個階段需要保留前k大的方案 設di,k為前i天第k大的方案, 每次考慮某條左端點為j的線段x時, 設數組gk = dj,k+w,與di,k歸并取前k的元素 每考慮一條線段的時間復雜度為O(k), 因此總時間復雜度為O(D+kr)移動機器人 在二維網格上有許多機器人。每個機器人的狀態(tài)由(x, y, d)表示, 即位置和朝向(東南西北) . 每個機器人按照各自各自固定的指令執(zhí)行移動, 兩個機器人互不影響，同一個位置可以有多個機器人。指令有兩種, 轉身(左轉90，180或270度)和移動(按當前朝向移動一個單位) 在機器人開始移動前，可以去掉一些

46、指令，改變機器人的行動路線和最終位置。刪除最少的指令讓所有機器人到達同一個最終位置 指令數不超過50分析 首先求出每個機器人能到達的范圍和每個點需要刪除的最少指令分析 每個機器人的指令數目不大于50，這就將機器人活動的范圍限制以初始位置為中心，邊長為50的正方形中。 機器人的位移用二元組(x, y)(-50 x,y50)表示，方向合起來表示一個狀態(tài)。 設di,x,y,k表示前i條指令執(zhí)行后到達狀態(tài)(x,y,k), 需要最少刪除多少條指令 用更新法做狀態(tài)轉移, 決策是O(1)的(刪還是不刪), 時間O(n2), R個機器人共O(Rn2)分析 然后再求出最優(yōu)點. 每次求交集, 去掉不可能的點, 同

47、時記錄剩下點需要刪除的指令最小值, 處理完所有機器人即可 求交集的方法可以用增量法, 逐個判斷集合i是否在前i-1個集合的交中 方法一:用排序二叉樹, 查找和刪除都是O(logn)的 方法二:用二維數組記錄第1個機器周圍的n2個格子是否在集合中, 查找和刪除都是O(1)的 最終時間復雜度為O(Rn2)佳佳的筷子 中國人吃飯喜歡用筷子。佳佳與常人不同，他的一雙筷子有三只，一雙短筷子加上一根比較長的（一般用來穿香腸之類的食物）。兩只較短的筷子的長度應該盡可能接近，但是最長的那根長度是無所謂的。如果一雙筷子的長度分別是A，B，C(ABC)，則用(A-B)2的值表示這雙筷子的質量，這個值越小，這雙筷子的質量越高。 佳佳請朋友吃飯，并準備為每人準備一雙這種特殊的筷子。佳佳有N（N5 000）只筷子，他希望找到一種辦法搭配好K雙筷子，使得這些筷子的質量值和最小分析 任一副筷子中A和B一定長度相鄰. 證明如下 對于某副筷子（A1,B1,C1）和另一副筷子（A2,B2,C2），如果A1=A2=B1=B2，那么交換一下筷子重新組合成（A1,A2,C1）和（B1,B2,C2）質量和會更優(yōu)。 對于某副筷子（A,B,C）和閑置的筷子D，如果A