入門動態(tài)規(guī)劃狀態(tài)壓縮

1、主講：主講：ftfish (ftfish (周偉周偉 天津大學天津大學20072007級級) )郵箱：郵箱：zhouwei- (zhouwei- (三個減號三個減號) )手機：手機： Q Q Q Q ：155 175 157155 175 157 信息學發(fā)展勢頭迅猛，信息學奧賽的題目來源遍及各行各業(yè)，經常有一些在實際應用中很有價值的問題被引入信息學并得到有效解決。 然而有一些問題卻被認為很可能不存在有效的(多項式級的)算法，這里以對幾個例題的剖析，簡述狀態(tài)壓縮思想及其應用。名稱名稱C/C+樣式樣式Pascal樣式樣式簡記法則簡記法則按位與按位與&and全一則一，否則為零全一則一，否則為零按位或

2、按位或|or有一則一，否則為零有一則一，否則為零按位取反按位取反not是零則一，是一則零是零則一，是一則零按位異或按位異或xor不同則一，相同則零不同則一，相同則零左移位左移位shlashrak等價于等價于a/2k作為對下文的準備，這里先為使用Pascal的OIers簡要介紹一下C/C+樣式的位運算(bitwise operation)。其優(yōu)先級：notandxoror位運算的特殊應用位運算的特殊應用and：用以取出一個數的某些二進制位用以取出一個數的某些二進制位取出一個數二進制中的最后一個取出一個數二進制中的最后一個1(lowbit)：x&-xor ：將一個數的某些位設為：將一個數的某些位設

3、為1not：間接構造一些數：間接構造一些數：0u= =232-1xor：不使用中間變量交換兩個數：不使用中間變量交換兩個數：a=ab;b=ba;a=ab;將一個數的某些位取反將一個數的某些位取反 在n*n(n20)的方格棋盤上放置n個車(可以攻擊所在行、列)，求使它們不能互相攻擊的方案總數。 10秒時間思考 這個題目之所以是作為引例而不是例題，是因為它實在是個非常簡單的組合學問題 我們一行一行放置，則第一行有n種選擇，第二行n-1，最后一行只有1種選擇，根據乘法原理，答案就是n! 這里既然以它作為狀態(tài)壓縮的引例，當然不會是為了介紹組合數學。我們下面來看另外一種解法：狀態(tài)壓縮遞推(States

4、Compressing Recursion,SCR) 我們仍然一行一行放置。 取棋子的放置情況作為狀態(tài)，某一列如果已經放置棋子則為1，否則為0。這樣，一個狀態(tài)就可以用一個最多20位的二進制數表示。 例如n=5,第1、3、4列已經放置，則這個狀態(tài)可以表示為01101(從右到左)。設fs為達到狀態(tài)s的方案數，則可以嘗試建立f的遞推關系。 考慮n=5,s=01101 因為我們是一行一行放置的，所以當達到s時已經放到了第三行。又因為一行能且僅能放置一個車，所以我們知道狀態(tài)s一定來自： 前兩行在第3、4列放置了棋子(不考慮順序，下同)，第三行在第1列放置； 前兩行在第1、4列放置了棋子，第三行在第3列放

5、置； 前兩行在第1、3列放置了棋子，第三行在第4列放置。 這三種情況互不相交，且只可能有這三種情況，根據加法原理，fs應該等于這三種情況的和。寫成遞推式就是： 根據上面的討論思路推廣之，得到引例的解決辦法：其中s的右起第i+1位為1(其實就是在枚舉s的二進制表示中的1)Prog P0read(n);int64 f1.220=0;f0=1;for(int i=1;i0;t-=t&-t)fi+=fi(t&-t);write(f2n-1); 反思這個算法，其正確性毋庸置疑(可以和n!對比驗證) 但是算法的時間復雜度為O(n2n)，空間復雜度O(2n)，是個指數級的算法，比循環(huán)計算n!差了好多，它有什

6、么優(yōu)勢？ （還有一個很的用處，即對新手說：“來看看我這個計算n!的程序，連這都看不懂就別OI了”）可擴展性！可擴展性！ 在n*n(n20)的方格棋盤上放置n個車，某些格子不能放，求使它們不能互相攻擊的方案總數。 30s思考時間 對于這個題目，如果組合數學學得不夠扎實，應該很難一眼看出解法。 本題確實存在數學方法(容斥原理)，但因為和引例同樣的理由，這里不再贅述。 引例的算法是在枚舉當前行(即s中1的個數，設為r)的放置位置(即枚舉每個1) 而對于例1，第r行可能存在無法放置的格子，怎么解決？ 事實上，我們并不需要對引例的算法進行太大的改變，只要在枚舉s中的1的時候判斷一下是否是不允許放置的格子

7、即可 然而對于n=20，O(n2n)的復雜度已經不允許我們再進行多余的判斷。所以實現這個算法時應該應用一些技巧。 我們用ar表示第r行不允許放置的情況，如果第r行某一位不允許放置則ar此位為0，否則為1，這可以在讀入數據階段完成 然后對于需要處理的狀態(tài)s，用ts=s&ar來代替s進行枚舉，即不枚舉s中的1轉而枚舉ts中的1。 因為ts保證了不允許放置的位為0，這樣就可以不用其它的判斷來實現算法 代碼中只增加了計算a數組和r的部分，而時間復雜度沒有變化。 我們直接套用引例的算法就使得看上去更難的例1得到了解決。 雖然這題用容斥原理更快，但容斥原理在這題上只有當棋盤為正方形、放入的棋子個數為n、且

8、棋盤上禁止放置的格子較少時才有較簡單的形式和較快的速度。 如果再對例1進行推廣，要在m*n的棋盤上放置k個車，那么容斥原理是無能為力的，而SCR算法只要進行很少的改變就可以解決問題。這也體現出了引例中給出的算法的擴展?jié)摿Α?有一個n*m的棋盤(n、m80,n*m80)要在棋盤上放k(k20)個棋子，使得任意兩個棋子不相鄰。求合法的方案總數 5min思考、討論、提問時間 觀察題目給出的規(guī)模，n、m80，這個規(guī)模要想用SC是困難的，280無論在時間還是空間上都無法承受 然而我們還看到n*m80 稍微思考我們可以發(fā)現：9*9=8180，即如果n,m都大于等于9，將不再滿足n*m80這一條件。所以，我

9、們有n或m小于等于8，而28是可以承受的！ 我們假設mn，n是行數m是列數，則每行的狀態(tài)可以用m位的二進制數表示 但是本題和例1又有不同：例1每行每列都只能放置一個棋子，而本題卻只限制每行每列的棋子不相鄰 上例中枚舉當前行的放置方案的做法依然可行。我們用數組s保存一行中所有的num個放置方案，則s數組可以在預處理過程中用DFS求出，同時用ci保存第i個狀態(tài)中1的個數以避免重復計算 開始設計狀態(tài)。本題狀態(tài)的維數需要增加，原因在于并不是每一行只放一個棋子，也不是每一行都要求有棋子，原先的表示方法已經無法完整表達一個狀態(tài)。 我們用fi,j,k表示第i行的狀態(tài)為sj且前i行總共放置k個棋子（下面用pn

10、代替原題中的k）的方案數。沿用枚舉當前行方案的做法，只要當前行的放置方案和上一行的不沖突。微觀地講，就是要兩行的狀態(tài)s1和s2中沒有同為1的位即可，亦即s1&s2=0 然而，雖然我們枚舉了第i行的放置方案，但卻不知道其上一行(第i-1行)的方案 為了解決這個問題，我們不得不連第i-1行的狀態(tài)一起枚舉，則可以寫出遞推式：其中其中s1=0s1=0，即在當前行不放置棋子；，即在當前行不放置棋子；j j和和p p是需要枚舉的兩個狀態(tài)編號。是需要枚舉的兩個狀態(tài)編號。 本題至此基本解決。當然，實現上仍有少許優(yōu)化空間，例如第i行只和第i-1行有關，可以用滾動數組節(jié)省空間。 這個算法時間復雜度O(n*pn*n

11、um2)，空間復雜度(滾動數組)O(pn*num) 運用簡單的組合數學知識可以求出本題中的num=144，因而對于本題的數據規(guī)?？梢院芸斐鼋?給出一個n*m(n100,m10)的棋盤，一些格子不能放置棋子。求最多能在棋盤上放置多少個棋子，使得每一行每一列的任兩個棋子間至少有兩個空格。 題目來源：NOI2001炮兵陣地 TOI 1023；POJ 1185 30s 思考時間 仍然先用DFS搜出一行可能狀態(tài)s，依舊用c保存s中1的個數，依照例1的預處理搞定不能放置棋子的格子（應該有這種意識） 問題是，這個題目的狀態(tài)怎么選？繼續(xù)像例2那樣似乎不行，原因在于棋子的攻擊范圍加大了 但是我們照葫蘆畫瓢：例2

12、的攻擊范圍只有一格，所以我們的狀態(tài)中只需要有當前行的狀態(tài)，再枚舉上一行的狀態(tài)即可進行遞推；而本題攻擊范圍是兩格，因此增加一維來表示上一行的狀態(tài)。 用fi,j,k表示第i行狀態(tài)為sj、第i-1行狀態(tài)為sk時前i行至多能放置的棋子數。則狀態(tài)轉移方程很容易寫出：顯然，算法時間復雜度為O(n*num3)，空間復雜度(滾動數組)O(num2)因為棋子攻擊范圍為兩格，可以直觀地想像到本題的num不會很大。的確，可以算出本題num60。 此算法還有優(yōu)化空間 我們分別枚舉了三行的狀態(tài)，還需要對這三個狀態(tài)進行是否沖突的判斷，這勢必會重復枚舉到一些沖突的狀態(tài)組合 在DFS出s后，我們可以算出哪些狀態(tài)對可以分別作為

13、兩行的狀態(tài)，這樣在DP時就不需要進行盲目的枚舉，理論上效率會更高。但因為num本身很小，所以這樣修改沒有顯著地減少運行時間 值得一提的是，本題筆者的算法雖然在理論上并不是最優(yōu)（有種應用三進制的方法），但由于位運算的使用，截至07年8月17日，筆者的程序在PKU OJ上長度最短，速度第二快。 但是很不幸，公元2007年8月18日，天津大學06級的某同學去掉本算法的一些關鍵判斷，達到了更短的長度，但其速度慢了3倍 這個題目是國內比賽中較早出現的狀態(tài)壓縮題。它告訴我們狀態(tài)壓縮不僅可以像前幾個例題那樣求方案數，而且可以求最優(yōu)方案，即狀態(tài)壓縮思想既可以應用到遞推上(SCR)，又可以應用到DP上(SCDP

14、)，更說明其有廣泛的應用空間。 看了這么多棋盤模型應用狀態(tài)壓縮的實例，可能會讓人產生錯覺，以為狀態(tài)壓縮只在棋盤上放棋子的題目中有用。我們暫時轉移視線，來看看狀態(tài)壓縮在其他地方的應用覆蓋模型。 給出n*m(1n、m11)的方格棋盤，用1*2的長方形骨牌不重疊地覆蓋這個棋盤，求覆蓋滿的方案數。 經典問題 TOJ 1343; POJ 2411Have a break ! 這也是個經典的組合數學問題：多米諾骨牌完美覆蓋問題(或所謂二聚物問題)。有很多關于這個問題的結論，甚至還有個專門的公式:2211)1+n*j(cos4)1+m*i(4cos22mnij誰看得懂、記得??？ 顯然，如果n、m都是奇數則無

15、解(由棋盤面積的奇偶性知)，否則必然有至少一個解(很容易構造出) 因此假設n、m至少有一個偶數，且mn 我們依然像前面的例題一樣把每行的放置方案DFS出來，逐行計算 用fi,s表示把前i-1行覆蓋滿、第i行覆蓋狀態(tài)為s的覆蓋方案數 因為在第i行上放置的骨牌最多也只能影響到第i-1行，則容易得遞推式： 首先討論DFS的一些細節(jié)。 對于當前行每一個位置，我們有3種放置方法： 豎直覆蓋，占據當前格和上一行同一列的格； 水平覆蓋，占據當前格和該行下一格； 不放置骨牌，直接空格。 如何根據這些枚舉出每個(s1,s2)呢？下面介紹兩種方法。 DFS共5個參數，分別為：p(當前列號)，s1、s2(當前行和上

16、一行的覆蓋情況)，b1、b2(上一列的放置對當前列兩行的影響，影響為1否則為0)。初始時s1=s2=b1=b2=0。 p=p+1，s1=s1*2+1，s2=s2*2（注意：第i行的放置方案用到第i-1行的某格時，s2中該格應為0！），b1=b2=0； p=p+1，s1=s1*2+1，s2=s2*2+1，b1=1，b2=0； p=p+1，s1=s1*2，s2=s2*2+1，b1=b2=0。 當p移出邊界且b1=b2=0時記錄此方案。 觀察第一種方法，發(fā)現b2始終為0，知這種方法有一定的冗余。換個更自然的方法，去掉參數b1、b2。 p=p+1，s1=s1*2+1，s2=s2*2； p=p+2，s1

17、=s1*4+3，s2=s2*4+3； p=p+1，s1=s1*2，s2=s2*2+1。 當p移出邊界時記錄此方案。 這樣，我們通過改變p的移動距離成功簡化了DFS過程，而且這種方法更加自然。 DFS過程有了，實現方法卻還有值得討論的地方 前面的例題中，我們?yōu)槭裁纯偸前逊胖梅桨窪FS預處理保存起來？是因為不合法的狀態(tài)太多，每次都重新DFS太浪費時間。 然而回到這個題目，特別是當采用第二種時，我們的DFS過程中甚至只有一個判斷(遞歸邊界)，說明根本沒有多少不合法的方案，也就沒有必要把所有方案保存下來，對于每行都重新DFS即可 這個算法時間復雜度為多少呢？因為DFS時以兩行為對象，每行2m，共進行n

18、次DFS，所以是O(n*4m)？ 這會使人誤以為本算法無法通過1n、m11的測試數據，而實際上本算法可以瞬間給出m=10,n=11時的解 為了計算精確的復雜度，必須先算出DFS得到的方案數。 考慮當前行的放置情況。 如果每格只有兩個選擇，則應該有2m種放置方案；如果每格有這3個選擇，且中p只移動一格，則應該有3m種放置方案。 然而現在的事實是：每格有這3個選擇，但中p移動2格，所以可以知道方案數應該在2m和3m之間 考慮第i列，則其必然是： 第i-1列采用達到； 第i-2列采用達到。 設hi表示前i列的方案數，則得到hi的計算式： 注意到式子的第二項是多個絕對值小于1的數的乘積，其對整個hm的

19、影響甚小，故略去，得到方案數hm0.85*2.414m，符合2mhm3m的預想。 因為總共進行了n次DFS，每次復雜度為O(hm)，所以算法總時間復雜度為O(n*hm)=O(n*0.85*2.414m)，對m=10,n=11不超時也就不足為奇了。應用滾動數組，空間復雜度為O(2m)。 給出n*m(1n、m9)的方格棋盤，用1*2的矩形的骨牌和L形的(2*2的去掉一個角)骨牌不重疊地覆蓋，求覆蓋滿的方案數。 SGU.131Hardwood Floor 觀察題目條件，只不過是比上例多了一種L形的骨牌。又因為本題中兩種骨牌的最大長度和上例一樣，所以本題的狀態(tài)表示與轉移方程與上例完全一樣。 上例中有兩

20、種DFS方案，其中第二種實現起來較第一種簡單。但在本題中，新增的L形骨牌讓第二種DFS難以實現，故回到第一種DFS。覆蓋情況 條件 參數 s 變化 參數 b 變化 1 0 0 0 0 無 s1 =s1 *2+b1 s2=s2*2 +1 -b2 b1 =0 b2=0 2 0 0 1 1 b1 =0 s1 =s1 *2 +1 s2=s2*2 +1 -b2 b1 = 1 b2=0 3 1 0 1 0 b1 =0 b2=0 s1 =s1 *2 +1 s2=s2*2 b1 =0 b2=0 4 1 0 1 1 b1 =0 b2=0 s1 =s1 *2 +1 s2=s2*2 b1 = 1 b2=0 5 0

21、1 1 1 b1 =0 s1 =s1 *2 +1 s2=s2*2 +1 -b2 b1 = 1 b2= 1 6 1 1 0 1 b2=0 s1 =s1 *2+b1 s2=s2*2 b1 = 1 b2= 1 7 1 1 1 0 b1 =0 b2=0 s1 =s1 *2 +1 s2=s2*2 b1 =0 b2= 1 容易看出，在本題中此種DFS方式實現很簡單，只要耐心認真實現各種情況。 因為L形骨牌不太規(guī)則，筆者沒能找到方案數的一維遞推公式，因此無法給出復雜度的解析式。但當m=9時，算法共生成放置方案79248個，則對于n=m=9,算法的復雜度為O(9*79248)，可以瞬間出解 和上例一樣，本題也沒有必要保存所有放置方案，同時也避免MLE 棋盤是SCR、SCDP算法很好的用武之地。 上面的例子的很多擴展都可以用SC來解決。 例如新的骨牌形狀：2*3、1*k（k較?。┑?應用的方式一般為把行或列當成階段，把每行的放置方案當狀態(tài)，通過枚舉所有放置方案進行轉移。 上面通過對幾個經典的應用狀態(tài)壓縮的題目的詳解，從應用的角度描述了狀態(tài)壓縮的一般思路。那么如何理解其本質呢？ 縱觀上文討論的題目，幾乎都是普普通通的一個遞推公式或者狀態(tài)