一類典型的動態(tài)規(guī)劃問題解析長沙市雅禮中學朱全民(難待學習)

1、一類典型動態(tài)規(guī)劃問題解析1Censored! 給定N個單詞，M個字符?，F(xiàn)在問你在長度為len的所有可能句子中。不出現(xiàn)給定的任何一個單詞有多少種可能。(n=10,m=50,len=50)2一道簡單問題問題描述:用26個英文字母作不允許重復的全排列，要求排除dog，god，gum，depth，thing字樣的出現(xiàn)，求滿足這些條件的排列數(shù)。用容斥原理解決!3分析 出現(xiàn)dog字樣的排列，相當于把dog作為一個單元參加排列，故類似有： 由于god,dog不可能在一個排列中同 時出現(xiàn)，故： 類似：4 由于gum,dog可以在dogum字樣中同時出現(xiàn)，故有： 類似有god和depth可以在godepth字樣

2、中同時出現(xiàn)，故 god和thing可以在thingod字樣中同時出現(xiàn)，從而 分析5分析6分析 由于god、depth、thing不可以同時出現(xiàn)，故有： 其余多于3個集合的交集都為空集。 故滿足要求的排列數(shù)為：7分析時間復雜度容斥原理需要求任意兩個集合,三個集合的交集對于n個單詞,時間復雜度為O(2n)。對于任意兩個單詞,需要判斷兩個單詞是否有相同部分.這需要用模式匹配的算法來進行分析,時間復雜度跟單詞的長度成正比。容斥原理的計算,需要用高精度乘法。因此,整的時間復雜度為O(單詞總長度 * 2n *高精度)。n=10,m=50,len=50,這個時間復雜度有點大!8回到原題舉例分析3個字符QWE

3、不能出現(xiàn)QQ,Q,WEE。長度為3的句子一共有7個,WEW,EWW,EWE,EEW,EEE9考慮下面這樣一顆單詞樹每個點實際上表示了一個單詞。也就是從根節(jié)點走到這個點路上的字符加起來。如右圖的3個葉子節(jié)點。設Ci表示第i個點代表的字符。由于每個節(jié)點連出去的邊可能沒有M條，那么我們把缺少的邊都補成虛邊。設C=Ci+虛邊上的字符.由于不存在Cj=C。那么虛邊指向的節(jié)點就是在C中出現(xiàn)的最長后綴。10分析如右圖，我們補充了一個ab節(jié)點的虛邊設Fi,j表示用了i個字符走到了j這個節(jié)點?？紤]Fi,j的意義？Fi,j意味著這i個字符組成的串出現(xiàn)在單詞樹中的最長后綴為Cj。11樣例分析12這樣我們很容易寫出狀

4、態(tài)轉移方程Fi,j=Fi-1,k(j不是葉子節(jié)點,k通過某條實邊或虛邊能到達j)邊界為F0,0=1(0為根節(jié)點)答案就是Flen,i(i非葉子節(jié)點)時間復雜度O(len*(節(jié)點總數(shù))*m*高精度)=O(50*500*50*20)=O(25*106)13Blocks Jimmy最近迷上了一款叫做方塊消除的游戲. 游戲規(guī)則如下：n個帶顏色方格排成一列，相同顏色的方塊連成一個區(qū)域（如果兩個相鄰的方塊顏色相同，則這兩個方塊屬于同一個區(qū)域). 游戲時，你可以任選一個區(qū)域消去.設這個區(qū)域包含的方塊數(shù)為x,則將得到x2的分值.方塊消去之后，右邊的方格將向左移動.雖然游戲很簡單，但是要得到高分也不是很容易.J

5、immy希望你幫助他找出最高可以得到多少分N200.14Sample如圖，依次消去灰,白,黑區(qū)域，你將得到42+32+22=29分，這是最高得分.15算法分析合并顏色序列，如 1 1 1 3 3 2 4 4 4 5 5 根據(jù)方塊消除的規(guī)則，連在一起的相同顏色方塊可以合并。 上面的顏色序列為(1,3),(3,2),(2,1),(4,3),(5,2),其中(a,b)表示有b個顏色為a的連在一起.于是題目可以表示成colori,leni,1=i=m, m表示顏色序列總共有m段. 上面的顏色序列中, m = 5, color1 . 5=(1,3,2,4,5)len 1 . 5=(3,2,1,3,2)1

6、6定義狀態(tài)設S(i,j,k)為(colori,leni),(colori+1,leni+1) (colorj-1,lenj-1)的連續(xù)同色整段以及在一系列消除操作后j后接了k個顏色為colorj的方塊(colorj,lenj+k)的一個顏色序列.設f(i,j,k)表示消除S(i,j,k)這一個顏色序列可以得到的最大分值.算法分析17算法分析動態(tài)規(guī)劃轉移如果立刻將(colorj,lenj+k)這一段消除，則轉移為f(i,j-1,0)+(lenj+k)2如果lenj+k暫時不消除而連接到上一個顏色相同的塊上,則轉移為f(i,p,k+lenj)+f(p+1,j-1,0). 其中colorp=colo

7、rj, i=pj18動態(tài)規(guī)劃轉移方程 f(i,j,k)=Maxf(i,j-1,0)+(lenj+k)2, f(i,p,k+lenj)+f(p+1,j-1,0)算法分析初值 f(i,i-1,0)=0答案 f(1,m,0)時間復雜度 O(n4)空間復雜度 O(n3)19注意細節(jié)1. 計算Restj表示第j塊后面有多少個顏色 為colorj的方塊，以確定k的范圍.2. p不需要直接從i到j-2枚舉，因為要求 colorpcolorj.計算Prevj表示j之前最 后一個與j同色的塊. 計算就可以順著j找到p=prevj, p=prevp 直到pi為止.20Robots 在一個n*m的棋盤內，一些格子里

8、有垃圾要拾撿?，F(xiàn)在有一個能撿垃圾的機器人從左上格子里出發(fā)，每次只能向右或者向下走。每次他到達一個點，就會自動把這個點內的垃圾拾掉。問：最多能拾多少垃圾。在最多的情況下，有多少種方案？請舉出一種方案來。數(shù)據(jù)范圍:n=100,m=10021舉例最多能拾5塊。有4種方法。22分析因為只能向右或者向下走。也就是說不能走回頭路。于是考慮動態(tài)規(guī)劃。設Fi,j表示從(1,1)點開始走到(i,j)的時候，最多撿了多少垃圾。Gi,j表示在fi,j最大的時候，有多少種方案。Ci,j=1表示(i,j)點有垃圾。Ci,j=0表示沒有。23狀態(tài)轉移方程根據(jù)(i,j)只能從(i-1,j)或者(i,j-1)走過來。于是fi

9、,j=Maxfi-1,j,fi,j-1+ci,j.gi,j=gi-1,j*k+gi,j-1*L。如果fi-1,j+ci,j=fi,j，則K=1否則K=0。如果fi,j-1+ci,j=fi,j，則L=1否則L=0。24總結于是我們得到第1，2問的答案。對于第3問，我們只要簡單得在動態(tài)規(guī)劃的時候記錄一個決策即從哪個方向走過來的就可以了。時間復雜度O(nm)。25附加問題1怎樣使得最少的機器人撿完所有的垃圾？在這個圖中，我們只需要2個機器人就能撿完所有的垃圾。26考慮這些機器人組成的路徑假設1號機器人組成的路徑是A11,A12,A13.2號機器人的路徑是A21,A22,A23(Aij代表一個垃圾的位

10、置)假設看成A12和A11配對，A13和A12配對，A22和A21配對，A23和A22配對的話那么N個點一組配對就對應了一組機器人和他們的路徑。27繼續(xù)分析考慮每一個機器人的路徑中只有起始點Ai1 這1個點沒有配對的點，也就是說在N個點的一次配對中，有多少個沒有配對的點，也就有多少組路徑。配對？配對最多的點？這讓我們想起了二分圖的最大匹配。28于是我們的算法流程這樣的：1.構造2分圖：如果一個垃圾點X能向右或者向下走能到達垃圾點Y。則連一條X-Y的邊。2.求最大匹配T。3.所有的垃圾站tot-|T|就是我們要求得答案。 方案按照上文所說，路徑上每一個點I緊跟在二分圖中i所匹配的點j后面即可。2

11、9總結巧妙的轉化關系是這道題目的關鍵。時間復雜度:O(最大匹配的時間復雜度)=O(tot3)tot為垃圾點的個數(shù)。30附加問題2假設要讓K個機器人撿完所有的垃圾。如何使得撿垃圾最多的人最少。31分析K=2或者k=3的時候，可以考慮使用動態(tài)規(guī)劃。Fx1,x2.xk,y1,y2.yk表示當前這k個人為于x1.xk這3個位置，且x1.xk左上沒有垃圾了。這k個人分別撿了y1.yk個垃圾。K更大的時候，可以考慮采用搜索+剪枝。因為問題的方案很多。所以有比較好的效果。32Hotel 有N個男人，M個女人，其中有C對夫婦要住房?，F(xiàn)在有P個房子。每個房子有個費用Ci和床位Bi。住房有以下要求:1.每個房子住

12、的人數(shù)不能超過Bi2.一個房間住了夫婦，不能再住其他人。3.不考慮夫婦情況下：一個房間住了男人后，不能再住女人。對女人也是一樣。問最少的費用。(n500,m500,P500,Bisize,lsize) ，那么肯定無論如何Ci/Bi最小的那些房間肯定會被選到。于是我們可以貪心在ksize,lsize的時候，給他們安排Ci/Bi最小的房間。然后再進行動態(tài)規(guī)劃。由于Bi=5.所以size=20就夠了。這樣時間復雜度就很低了。36Distributing tasks 給你一個2*n的矩陣。每個方格內有一個任務難度為Ci,j?，F(xiàn)在你有M個人。每個人將會完成一定量的任務：這個任務或是在矩陣內一段1*k內的

13、任務或是矩陣內一段2*k的任務。每個人的任務量就是完成任務的難度和。要求每個人的任務不重復，且矩陣內的所有任務都要完成?，F(xiàn)在問你任務量最多的那個人至少要完成多少。n10001, m=min2*n,1000. 37舉例分析如下圖所是，紅，黃，綠分別代表3個人。每個人的任務量都是6。38分析對于這類要求最大的最小問題，我們還是首選二分答案。假設當前每局的答案T。也就是說每個人的任務量上限都為T。我們只要判斷能否把2*n的矩陣割成L塊(L=m)使得每塊任務量=T。39考慮動態(tài)規(guī)劃設Fi表示第1列到第i列被切割完后，使用的最少人數(shù)。如果第i列是被一個2*k的矩陣覆蓋了。那么我們維護一個指針就可以在均攤O(n)內算出所有的這種情況Fi=Minfi,fj+140考慮是被一些1*k的矩陣覆蓋由于這個時候2行之間沒有關系，那么我們當然從后往前考慮每一段，現(xiàn)在每一段能做的任務越多越好。這樣我們得出了一個有效的算法。維護2個指針P,Q。一開始位置都在i。每次找到P,Q