狀態(tài)壓縮(優(yōu)秀課件)

狀態(tài)壓縮1醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮1醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮信息學(xué)發(fā)展勢(shì)頭迅猛，信息學(xué)奧賽的題目來(lái)源遍及各行各業(yè)，經(jīng)常有一些在實(shí)際應(yīng)用中很有價(jià)值的問題被引入信息學(xué)并得到有效解決。然而有一些問題卻被認(rèn)為很可能不存在有效的(多項(xiàng)式級(jí)的)算法，這里以對(duì)幾個(gè)例題的剖析，簡(jiǎn)述狀態(tài)壓縮思想及其應(yīng)用。2醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮信息學(xué)發(fā)展勢(shì)頭迅猛，信息學(xué)奧賽的題目來(lái)源遍及各行各業(yè)狀態(tài)壓縮

——預(yù)備知識(shí)作為對(duì)下文的準(zhǔn)備，這里先為使用Pascal的OIers簡(jiǎn)要介紹一下C/C++樣式的位運(yùn)算(bitwiseoperation)。其優(yōu)先級(jí)：not>and>xor>or3醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——預(yù)備知識(shí)作為對(duì)下文的準(zhǔn)備，這里先為使用Pasc狀態(tài)壓縮

——預(yù)備知識(shí)位運(yùn)算的特殊應(yīng)用and：用以取出一個(gè)數(shù)的某些二進(jìn)制位取出一個(gè)數(shù)二進(jìn)制中的最后一個(gè)1(lowbit)：x&-xor：將一個(gè)數(shù)的某些位設(shè)為1not：間接構(gòu)造一些數(shù)：~0u=4294967295=232-1xor：不使用中間變量交換兩個(gè)數(shù)：a=a^b; b=b^a; a=a^b;將一個(gè)數(shù)的某些位取反4醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——預(yù)備知識(shí)位運(yùn)算的特殊應(yīng)用4醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——引例在n*n(n≤20)的方格棋盤上放置n個(gè)車(可以攻擊所在行、列)，求使它們不能互相攻擊的方案總數(shù)。10秒時(shí)間思考5醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——引例在n*n(n≤20)的方格棋盤上放置n個(gè)車狀態(tài)壓縮

——引例這個(gè)題目之所以是作為引例而不是例題，是因?yàn)樗鼘?shí)在是個(gè)非常簡(jiǎn)單的組合學(xué)問題我們一行一行放置，則第一行有n種選擇，第二行n-1，……，最后一行只有1種選擇，根據(jù)乘法原理，答案就是n!這里既然以它作為狀態(tài)壓縮的引例，當(dāng)然不會(huì)是為了介紹組合數(shù)學(xué)。我們下面來(lái)看另外一種解法：狀態(tài)壓縮遞推(StatesCompressingRecursion,SCR)6醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——引例這個(gè)題目之所以是作為引例而不是例題，是因?yàn)闋顟B(tài)壓縮

——引例解法我們?nèi)匀灰恍幸恍蟹胖?。取棋子的放置情況作為狀態(tài)，某一列如果已經(jīng)放置棋子則為1，否則為0。這樣，一個(gè)狀態(tài)就可以用一個(gè)最多20位的二進(jìn)制數(shù)表示。例如n=5,第1、3、4列已經(jīng)放置，則這個(gè)狀態(tài)可以表示為01101(從右到左)。設(shè)fs為達(dá)到狀態(tài)s的方案數(shù)，則可以嘗試建立f的遞推關(guān)系。7醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——引例解法我們?nèi)匀灰恍幸恍蟹胖谩?醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——引例解法考慮n=5,s=01101因?yàn)槲覀兪且恍幸恍蟹胖玫?，所以?dāng)達(dá)到s時(shí)已經(jīng)放到了第三行。又因?yàn)橐恍心芮覂H能放置一個(gè)車，所以我們知道狀態(tài)s一定來(lái)自：8醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——引例解法考慮n=5,s=011018醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——引例解法①前兩行在第3、4列放置了棋子(不考慮順序，下同)，第三行在第1列放置；②前兩行在第1、4列放置了棋子，第三行在第3列放置；③前兩行在第1、3列放置了棋子，第三行在第4列放置。9醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——引例解法①前兩行在第3、4列放置了棋子(不考慮狀態(tài)壓縮

——引例解法這三種情況互不相交，且只可能有這三種情況，根據(jù)加法原理，fs應(yīng)該等于這三種情況的和。寫成遞推式就是：10醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——引例解法這三種情況互不相交，且只可能有這三種情狀態(tài)壓縮

——引例解法根據(jù)上面的討論思路推廣之，得到引例的解決辦法：其中s的右起第i+1位為1(其實(shí)就是在枚舉s的二進(jìn)制表示中的1)11醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——引例解法根據(jù)上面的討論思路推廣之，得到引例的解狀態(tài)壓縮

——引例的實(shí)現(xiàn)ProgP0{ read(n); int64f[1..220]={0}; f[0]=1; for(inti=1;i<2n;i++) for(intt=i;t>0;t-=t&-t) f[i]+=f[i^(t&-t)]; write(f[2n-1]);}12醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——引例的實(shí)現(xiàn)ProgP012醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——對(duì)引例的思考反思這個(gè)算法，其正確性毋庸置疑(可以和n!對(duì)比驗(yàn)證)但是算法的時(shí)間復(fù)雜度為O(n2n)，空間復(fù)雜度O(2n)，是個(gè)指數(shù)級(jí)的算法，比循環(huán)計(jì)算n!差了好多，它有什么優(yōu)勢(shì)？（還有一個(gè)很…的用處，即對(duì)新手說(shuō)：“來(lái)看看我這個(gè)計(jì)算n!的程序，連這都看不懂就別OI了~”）可擴(kuò)展性！！13醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——對(duì)引例的思考反思這個(gè)算法，其正確性毋庸置疑(可狀態(tài)壓縮

——例1在n*n(n≤20)的方格棋盤上放置n個(gè)車，某些格子不能放，求使它們不能互相攻擊的方案總數(shù)。30s思考時(shí)間14醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例1在n*n(n≤20)的方格棋盤上放置n個(gè)車狀態(tài)壓縮

——例1分析對(duì)于這個(gè)題目，如果組合數(shù)學(xué)學(xué)得不夠扎實(shí)，應(yīng)該很難一眼看出解法。本題確實(shí)存在數(shù)學(xué)方法(容斥原理)，但因?yàn)楹鸵瑯拥睦碛桑@里不再贅述。引例的算法是在枚舉當(dāng)前行(即s中1的個(gè)數(shù)，設(shè)為r)的放置位置(即枚舉每個(gè)1)而對(duì)于例1，第r行可能存在無(wú)法放置的格子，怎么解決？枚舉1的時(shí)候判斷一下嘛！15醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例1分析對(duì)于這個(gè)題目，如果組合數(shù)學(xué)學(xué)得不夠扎實(shí)狀態(tài)壓縮

——例1解法事實(shí)上，我們并不需要對(duì)引例的算法進(jìn)行太大的改變，只要在枚舉s中的1的時(shí)候判斷一下是否是不允許放置的格子即可然而對(duì)于n=20，O(n2n)的復(fù)雜度已經(jīng)不允許我們?cè)龠M(jìn)行多余的判斷。所以實(shí)現(xiàn)這個(gè)算法時(shí)應(yīng)該應(yīng)用一些技巧。我們用ar表示第r行不允許放置的情況，如果第r行某一位不允許放置則ar此位為0，否則為1，這可以在讀入數(shù)據(jù)階段完成16醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例1解法事實(shí)上，我們并不需要對(duì)引例的算法進(jìn)行太狀態(tài)壓縮

——例1解法然后對(duì)于需要處理的狀態(tài)s，用ts=s&ar來(lái)代替s進(jìn)行枚舉，即不枚舉s中的1轉(zhuǎn)而枚舉ts中的1。因?yàn)閠s保證了不允許放置的位為0，這樣就可以不用其它的判斷來(lái)實(shí)現(xiàn)算法代碼中只增加了計(jì)算a數(shù)組和r的部分，而時(shí)間復(fù)雜度沒有變化。17醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例1解法然后對(duì)于需要處理的狀態(tài)s，用ts=s&狀態(tài)壓縮

——對(duì)例1的思考我們直接套用引例的算法就使得看上去更難的例1得到了解決。雖然這題用容斥原理更快，但容斥原理在這題上只有當(dāng)棋盤為正方形、放入的棋子個(gè)數(shù)為n、且棋盤上禁止放置的格子較少時(shí)才有較簡(jiǎn)單的形式和較快的速度。如果再對(duì)例1進(jìn)行推廣，要在m*n的棋盤上放置k個(gè)車，那么容斥原理是無(wú)能為力的，而SCR算法只要進(jìn)行很少的改變就可以解決問題。這也體現(xiàn)出了引例中給出的算法的擴(kuò)展?jié)摿Α?8醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——對(duì)例1的思考我們直接套用引例的算法就使得看上去狀態(tài)壓縮

——例2有一個(gè)n*m的棋盤(n、m≤80,n*m≤80)要在棋盤上放k(k≤20)個(gè)棋子，使得任意兩個(gè)棋子不相鄰。求合法的方案總數(shù)5min思考、討論、提問時(shí)間19醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例2有一個(gè)n*m的棋盤(n、m≤80,n*m≤狀態(tài)壓縮

——例2分析觀察題目給出的規(guī)模，n、m≤80，這個(gè)規(guī)模要想用SC是困難的，280無(wú)論在時(shí)間還是空間上都無(wú)法承受然而我們還看到n*m≤80稍微思考我們可以發(fā)現(xiàn)：9*9=81>80，即如果n,m都大于等于9，將不再滿足n*m≤80這一條件。所以，我們有n或m小于等于8，而28是可以承受的！20醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例2分析觀察題目給出的規(guī)模，n、m≤80，這個(gè)狀態(tài)壓縮

——例2分析我們假設(shè)m≤n，n是行數(shù)m是列數(shù)，則每行的狀態(tài)可以用m位的二進(jìn)制數(shù)表示但是本題和例1又有不同：例1每行每列都只能放置一個(gè)棋子，而本題卻只限制每行每列的棋子不相鄰上例中枚舉當(dāng)前行的放置方案的做法依然可行。我們用數(shù)組s保存一行中所有的num個(gè)放置方案，則s數(shù)組可以在預(yù)處理過程中用DFS求出，同時(shí)用ci保存第i個(gè)狀態(tài)中1的個(gè)數(shù)以避免重復(fù)計(jì)算21醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例2分析我們假設(shè)m≤n，n是行數(shù)m是列數(shù)，則每狀態(tài)壓縮

——例2分析開始設(shè)計(jì)狀態(tài)。本題狀態(tài)的維數(shù)需要增加，原因在于并不是每一行只放一個(gè)棋子，也不是每一行都要求有棋子，原先的表示方法已經(jīng)無(wú)法完整表達(dá)一個(gè)狀態(tài)。我們用fi,j,k表示第i行的狀態(tài)為sj且前i行總共放置k個(gè)棋子（下面用pn代替原題中的k）的方案數(shù)。沿用枚舉當(dāng)前行方案的做法，只要當(dāng)前行的放置方案和上一行的不沖突。微觀地講，就是要兩行的狀態(tài)s1和s2中沒有同為1的位即可，亦即s1&s2=022醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例2分析開始設(shè)計(jì)狀態(tài)。本題狀態(tài)的維數(shù)需要增加，狀態(tài)壓縮

——例2解法然而，雖然我們枚舉了第i行的放置方案，但卻不知道其上一行(第i-1行)的方案為了解決這個(gè)問題，我們不得不連第i-1行的狀態(tài)一起枚舉，則可以寫出遞推式：其中s1=0，即在當(dāng)前行不放置棋子；j和p是需要枚舉的兩個(gè)狀態(tài)編號(hào)。23醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例2解法然而，雖然我們枚舉了第i行的放置方案，狀態(tài)壓縮

——例2解法本題至此基本解決。當(dāng)然，實(shí)現(xiàn)上仍有少許優(yōu)化空間，例如第i行只和第i-1行有關(guān)，可以用滾動(dòng)數(shù)組節(jié)省空間。這個(gè)算法時(shí)間復(fù)雜度O(n*pn*num2)，空間復(fù)雜度(滾動(dòng)數(shù)組)O(pn*num)運(yùn)用簡(jiǎn)單的組合數(shù)學(xué)知識(shí)可以求出本題中的num=144，因而對(duì)于本題的數(shù)據(jù)規(guī)?？梢院芸斐鼋?4醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例2解法本題至此基本解決。當(dāng)然，實(shí)現(xiàn)上仍有少許狀態(tài)壓縮

——例3給出一個(gè)n*m(n≤100,m≤10)的棋盤，一些格子不能放置棋子。求最多能在棋盤上放置多少個(gè)棋子，使得每一行每一列的任兩個(gè)棋子間至少有兩個(gè)空格。題目來(lái)源：NOI2001《炮兵陣地》TOI1023；POJ118530s思考時(shí)間25醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例3給出一個(gè)n*m(n≤100,m≤10)的棋狀態(tài)壓縮

——例3分析仍然先用DFS搜出一行可能狀態(tài)s，依舊用c[]保存s[]中1的個(gè)數(shù)，依照例1的預(yù)處理搞定不能放置棋子的格子（應(yīng)該有這種意識(shí)）問題是，這個(gè)題目的狀態(tài)怎么選？繼續(xù)像例2那樣似乎不行，原因在于棋子的攻擊范圍加大了26醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例3分析仍然先用DFS搜出一行可能狀態(tài)s，依舊狀態(tài)壓縮

——例3分析但是我們照葫蘆畫瓢：例2的攻擊范圍只有一格，所以我們的狀態(tài)中只需要有當(dāng)前行的狀態(tài)，再枚舉上一行的狀態(tài)即可進(jìn)行遞推；而本題攻擊范圍是兩格，因此增加一維來(lái)表示上一行的狀態(tài)。27醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例3分析但是我們照葫蘆畫瓢：例2的攻擊范圍只有狀態(tài)壓縮

——例3解法用fi,j,k表示第i行狀態(tài)為sj、第i-1行狀態(tài)為sk時(shí)前i行至多能放置的棋子數(shù)。則狀態(tài)轉(zhuǎn)移方程很容易寫出：顯然，算法時(shí)間復(fù)雜度為O(n*num3)，空間復(fù)雜度(滾動(dòng)數(shù)組)O(num2)因?yàn)槠遄庸舴秶鸀閮筛瘢梢灾庇^地想像到本題的num不會(huì)很大。的確，可以算出本題num≤60。28醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例3解法用fi,j,k表示第i行狀態(tài)為sj、第狀態(tài)壓縮

——例3題外話此算法還有優(yōu)化空間我們分別枚舉了三行的狀態(tài)，還需要對(duì)這三個(gè)狀態(tài)進(jìn)行是否沖突的判斷，這勢(shì)必會(huì)重復(fù)枚舉到一些沖突的狀態(tài)組合在DFS出s[]后，我們可以算出哪些狀態(tài)對(duì)可以分別作為兩行的狀態(tài)，這樣在DP時(shí)就不需要進(jìn)行盲目的枚舉，理論上效率會(huì)更高。但因?yàn)閚um本身很小，所以這樣修改沒有顯著地減少運(yùn)行時(shí)間29醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例3題外話此算法還有優(yōu)化空間29醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例3題外話值得一提的是，本題筆者的算法雖然在理論上并不是最優(yōu)（有種應(yīng)用三進(jìn)制的方法），但由于位運(yùn)算的使用，截至07年8月17日，筆者的程序在PKUOJ上長(zhǎng)度最短，速度第二快。但是很不幸，公元2007年8月18日，天津大學(xué)06級(jí)的某同學(xué)去掉本算法的一些關(guān)鍵判斷，達(dá)到了更短的長(zhǎng)度，但其速度慢了3倍……30醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例3題外話值得一提的是，本題筆者的算法雖然在理狀態(tài)壓縮

——例3題外話這個(gè)題目是國(guó)內(nèi)比賽中較早出現(xiàn)的狀態(tài)壓縮題。它告訴我們狀態(tài)壓縮不僅可以像前幾個(gè)例題那樣求方案數(shù)，而且可以求最優(yōu)方案，即狀態(tài)壓縮思想既可以應(yīng)用到遞推上(SCR)，又可以應(yīng)用到DP上(SCDP)，更說(shuō)明其有廣泛的應(yīng)用空間。31醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例3題外話這個(gè)題目是國(guó)內(nèi)比賽中較早出現(xiàn)的狀態(tài)壓狀態(tài)壓縮

——新的模型看了這么多棋盤模型應(yīng)用狀態(tài)壓縮的實(shí)例，可能會(huì)讓人產(chǎn)生錯(cuò)覺，以為狀態(tài)壓縮只在棋盤上放棋子的題目中有用。我們暫時(shí)轉(zhuǎn)移視線，來(lái)看看狀態(tài)壓縮在其他地方的應(yīng)用——覆蓋模型。32醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——新的模型看了這么多棋盤模型應(yīng)用狀態(tài)壓縮的實(shí)例，狀態(tài)壓縮

——例4給出n*m(1≤n、m≤11)的方格棋盤，用1*2的長(zhǎng)方形骨牌不重疊地覆蓋這個(gè)棋盤，求覆蓋滿的方案數(shù)。。經(jīng)典問題TOJ1343;POJ2411Haveabreak!33醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例4給出n*m(1≤n、m≤11)的方格棋盤，狀態(tài)壓縮

——例4背景這也是個(gè)經(jīng)典的組合數(shù)學(xué)問題：多米諾骨牌完美覆蓋問題(或所謂二聚物問題)。有很多關(guān)于這個(gè)問題的結(jié)論，甚至還有個(gè)專門的公式:誰(shuí)看得懂、記得?。?？？34醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例4背景這也是個(gè)經(jīng)典的組合數(shù)學(xué)問題：多米諾骨牌狀態(tài)壓縮

——例4分析顯然，如果n、m都是奇數(shù)則無(wú)解(由棋盤面積的奇偶性知)，否則必然有至少一個(gè)解(很容易構(gòu)造出)因此假設(shè)n、m至少有一個(gè)偶數(shù)，且m≤n我們依然像前面的例題一樣把每行的放置方案DFS出來(lái)，逐行計(jì)算35醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例4分析顯然，如果n、m都是奇數(shù)則無(wú)解(由棋盤狀態(tài)壓縮

——例4解法用fi,s表示把前i-1行覆蓋滿、第i行覆蓋狀態(tài)為s的覆蓋方案數(shù)因?yàn)樵诘趇行上放置的骨牌最多也只能影響到第i-1行，則容易得遞推式：36醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例4解法用fi,s表示把前i-1行覆蓋滿、第i狀態(tài)壓縮

——例4細(xì)節(jié)首先討論DFS的一些細(xì)節(jié)。對(duì)于當(dāng)前行每一個(gè)位置，我們有3種放置方法：①豎直覆蓋，占據(jù)當(dāng)前格和上一行同一列的格；②水平覆蓋，占據(jù)當(dāng)前格和該行下一格；③不放置骨牌，直接空格。如何根據(jù)這些枚舉出每個(gè)(s1,s2)呢？下面介紹兩種方法。37醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例4細(xì)節(jié)首先討論DFS的一些細(xì)節(jié)。37醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例4DFS方法1DFS共5個(gè)參數(shù)，分別為：p(當(dāng)前列號(hào))，s1、s2(當(dāng)前行和上一行的覆蓋情況)，b1、b2(上一列的放置對(duì)當(dāng)前列兩行的影響，影響為1否則為0)。初始時(shí)s1=s2=b1=b2=0。①p=p+1，s1=s1*2+1，s2=s2*2（注意：第i行的放置方案用到第i-1行的某格時(shí)，s2中該格應(yīng)為0?。琤1=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。當(dāng)p移出邊界且b1=b2=0時(shí)記錄此方案。38醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例4DFS方法1DFS共5個(gè)參數(shù)，分別為：p狀態(tài)壓縮

——例4DFS方法2觀察第一種方法，發(fā)現(xiàn)b2始終為0，知這種方法有一定的冗余。換個(gè)更自然的方法，去掉參數(shù)b1、b2。①p=p+1，s1=s1*2+1，s2=s2*2；②p=p+2，s1=s1*4+3，s2=s2*4+3；③p=p+1，s1=s1*2，s2=s2*2+1。當(dāng)p移出邊界時(shí)記錄此方案。這樣，我們通過改變p的移動(dòng)距離成功簡(jiǎn)化了DFS過程，而且這種方法更加自然。39醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例4DFS方法2觀察第一種方法，發(fā)現(xiàn)b2始終狀態(tài)壓縮

——例4細(xì)節(jié)DFS過程有了，實(shí)現(xiàn)方法卻還有值得討論的地方前面的例題中，我們?yōu)槭裁纯偸前逊胖梅桨窪FS預(yù)處理保存起來(lái)？是因?yàn)椴缓戏ǖ臓顟B(tài)太多，每次都重新DFS太浪費(fèi)時(shí)間。然而回到這個(gè)題目，特別是當(dāng)采用第二種時(shí)，我們的DFS過程中甚至只有一個(gè)判斷(遞歸邊界)，說(shuō)明根本沒有多少不合法的方案，也就沒有必要把所有方案保存下來(lái)，對(duì)于每行都重新DFS即可40醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例4細(xì)節(jié)DFS過程有了，實(shí)現(xiàn)方法卻還有值得討狀態(tài)壓縮

——例4細(xì)節(jié)這個(gè)算法時(shí)間復(fù)雜度為多少呢？因?yàn)镈FS時(shí)以兩行為對(duì)象，每行2m，共進(jìn)行n次DFS，所以是O(n*4m)？這會(huì)使人誤以為本算法無(wú)法通過1≤n、m≤11的測(cè)試數(shù)據(jù)，而實(shí)際上本算法可以瞬間給出m=10,n=11時(shí)的解為了計(jì)算精確的復(fù)雜度，必須先算出DFS得到的方案數(shù)。41醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例4細(xì)節(jié)這個(gè)算法時(shí)間復(fù)雜度為多少呢？因?yàn)镈F狀態(tài)壓縮

——例4復(fù)雜度分析考慮當(dāng)前行的放置情況。如果每格只有①③兩個(gè)選擇，則應(yīng)該有2m種放置方案；如果每格有①②③這3個(gè)選擇，且②中p只移動(dòng)一格，則應(yīng)該有3m種放置方案。然而現(xiàn)在的事實(shí)是：每格有①②③這3個(gè)選擇，但②中p移動(dòng)2格，所以可以知道方案數(shù)應(yīng)該在2m和3m之間42醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例4復(fù)雜度分析考慮當(dāng)前行的放置情況。42醫(yī)藥狀態(tài)壓縮

——例4復(fù)雜度分析考慮第i列，則其必然是：第i-1列采用①③達(dá)到；第i-2列采用②達(dá)到。設(shè)hi表示前i列的方案數(shù)，則得到hi的計(jì)算式：43醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例4復(fù)雜度分析考慮第i列，則其必然是：43醫(yī)狀態(tài)壓縮

——例4復(fù)雜度分析注意到式子的第二項(xiàng)是多個(gè)絕對(duì)值小于1的數(shù)的乘積，其對(duì)整個(gè)hm的影響甚小，故略去，得到方案數(shù)hm≈0.85*2.414m，符合2m<hm<3m的預(yù)想。因?yàn)榭偣策M(jìn)行了n次DFS，每次復(fù)雜度為O(hm)，所以算法總時(shí)間復(fù)雜度為O(n*hm)=O(n*0.85*2.414m)，對(duì)m=10,n=11不超時(shí)也就不足為奇了。應(yīng)用滾動(dòng)數(shù)組，空間復(fù)雜度為O(2m)。44醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例4復(fù)雜度分析注意到式子的第二項(xiàng)是多個(gè)絕對(duì)值狀態(tài)壓縮

——例5給出n*m(1≤n、m≤9)的方格棋盤，用1*2的矩形的骨牌和L形的(2*2的去掉一個(gè)角)骨牌不重疊地覆蓋，求覆蓋滿的方案數(shù)。SGU.131《HardwoodFloor》45醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例5給出n*m(1≤n、m≤9)的方格棋盤，用狀態(tài)壓縮

——例5解法觀察題目條件，只不過是比上例多了一種L形的骨牌。又因?yàn)楸绢}中兩種骨牌的最大長(zhǎng)度和上例一樣，所以本題的狀態(tài)表示與轉(zhuǎn)移方程與上例完全一樣。上例中有兩種DFS方案，其中第二種實(shí)現(xiàn)起來(lái)較第一種簡(jiǎn)單。但在本題中，新增的L形骨牌讓第二種DFS難以實(shí)現(xiàn)，故回到第一種DFS。46醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例5解法觀察題目條件，只不過是比上例多了一種L狀態(tài)壓縮

——例5DFS參數(shù)47醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例5DFS參數(shù)47醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例5解法容易看出，在本題中此種DFS方式實(shí)現(xiàn)很簡(jiǎn)單，只要耐心認(rèn)真實(shí)現(xiàn)各種情況。因?yàn)長(zhǎng)形骨牌不太規(guī)則，筆者沒能找到方案數(shù)的一維遞推公式，因此無(wú)法給出復(fù)雜度的解析式。但當(dāng)m=9時(shí)，算法共生成放置方案79248個(gè)，則對(duì)于n=m=9,算法的復(fù)雜度為O(9*79248)，可以瞬間出解和上例一樣，本題也沒有必要保存所有放置方案，同時(shí)也避免MLE48醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例5解法容易看出，在本題中此種DFS方式實(shí)現(xiàn)很狀態(tài)壓縮

——棋盤小結(jié)棋盤是SCR、SCDP算法很好的用武之地。上面的例子的很多擴(kuò)展都可以用SC來(lái)解決。例如新的骨牌形狀：2*3、1*k（k較?。┑葢?yīng)用的方式一般為把行或列當(dāng)成階段，把每行的放置方案當(dāng)狀態(tài)，通過枚舉所有放置方案進(jìn)行轉(zhuǎn)移。49醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——棋盤小結(jié)棋盤是SCR、SCDP算法很好的用武狀態(tài)壓縮

——本質(zhì)上面通過對(duì)幾個(gè)經(jīng)典的應(yīng)用狀態(tài)壓縮的題目的詳解，從應(yīng)用的角度描述了狀態(tài)壓縮的一般思路。那么如何理解其本質(zhì)呢？50醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——本質(zhì)上面通過對(duì)幾個(gè)經(jīng)典的應(yīng)用狀態(tài)壓縮的題目的詳狀態(tài)壓縮

——本質(zhì)縱觀上文討論的題目，幾乎都是普普通通的一個(gè)遞推公式或者狀態(tài)轉(zhuǎn)移方程，只不過其中的一維或多維是“壓縮的”，即把一個(gè)狀態(tài)(一個(gè)方案、一個(gè)集合等)壓縮成一個(gè)整數(shù)。這很明顯是一個(gè)Hash的過程，所以SCDP又被稱為HashDP或集合DP。除去這一點(diǎn)區(qū)別，我們發(fā)現(xiàn)它和普通遞推/DP沒有什么差別，都是從已有的狀態(tài)推知新的狀態(tài)，所做的決策都沒有后效……那我們?yōu)槭裁匆脿顟B(tài)壓縮，即狀態(tài)壓縮的動(dòng)機(jī)是什么？51醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——本質(zhì)縱觀上文討論的題目，幾乎都是普普通通的一個(gè)狀態(tài)壓縮

——本質(zhì)動(dòng)機(jī)回想前述的題目，以多米諾骨牌覆蓋為例，如果我們不狀態(tài)壓縮，能否正確解答呢？先來(lái)進(jìn)行一下嘗試。嘗試fi表示前i行最多能放的骨牌數(shù)，我們發(fā)現(xiàn)這樣的表示方法太“粗糙”，根本無(wú)法表達(dá)出行與行之間因放置骨牌產(chǎn)生的細(xì)微的變化這樣的狀態(tài)表示無(wú)法得到正確的遞推或狀態(tài)轉(zhuǎn)移關(guān)系。因此我們?cè)黾訉⒚啃小凹?xì)化”為每格的一維，即狀態(tài)壓縮所以，狀態(tài)太粗糙以致無(wú)法正確轉(zhuǎn)移是狀態(tài)壓縮的一個(gè)動(dòng)機(jī)。52醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——本質(zhì)動(dòng)機(jī)回想前述的題目，以多米諾骨牌覆蓋為例狀態(tài)壓縮

——終例最后，以一個(gè)跟棋盤完全沒有關(guān)系的例子來(lái)結(jié)束這次狀態(tài)壓縮之旅給出一個(gè)有向圖(頂點(diǎn)數(shù)n≤20)，求這個(gè)圖的合法的拓?fù)湫蛄械膫€(gè)數(shù)。經(jīng)典問題53醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——終例最后，以一個(gè)跟棋盤完全沒有關(guān)系的例子來(lái)結(jié)束狀態(tài)壓縮

——終例解法既然是狀態(tài)壓縮，就要先確定取什么作為狀態(tài)。有了前面的介紹，應(yīng)該可以嘗試以已經(jīng)訪問過的點(diǎn)的集合作為狀態(tài)。狀態(tài)S表示當(dāng)前已經(jīng)訪問過的節(jié)點(diǎn)的集合，則fS表示訪問S中的點(diǎn)的合法的拓?fù)湫虻膫€(gè)數(shù)有了合適的狀態(tài)表示，再聯(lián)系遞推的一般思路，我們發(fā)現(xiàn)只需要枚舉最后到達(dá)的點(diǎn)即可。54醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——終例解法既然是狀態(tài)壓縮，就要先確定取什么作為狀態(tài)壓縮

——終例解法假設(shè)集合S中最后到達(dá)的點(diǎn)為x，則有：雖然我們描述此算法用的是集合的語(yǔ)言，但實(shí)現(xiàn)這個(gè)算法仍然是用二進(jìn)制 即S＝01101表示已經(jīng)訪問了頂點(diǎn)1、3、4要求x到S中剩余的點(diǎn)都沒有有向邊55醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——終例解法假設(shè)集合S中最后到達(dá)的點(diǎn)為x，則有：狀態(tài)壓縮

——總結(jié)狀態(tài)壓縮是一種思想，理論上在任何有“狀態(tài)”的算法中都可以應(yīng)用這里只是對(duì)其應(yīng)用進(jìn)行了簡(jiǎn)單的闡述經(jīng)過應(yīng)用的磨練，總有一天狀態(tài)壓縮會(huì)進(jìn)入每個(gè)Coder的潛意識(shí)中謝謝！56醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——總結(jié)狀態(tài)壓縮是一種思想，理論上在任何有“狀態(tài)”狀態(tài)壓縮57醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮1醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮信息學(xué)發(fā)展勢(shì)頭迅猛，信息學(xué)奧賽的題目來(lái)源遍及各行各業(yè)，經(jīng)常有一些在實(shí)際應(yīng)用中很有價(jià)值的問題被引入信息學(xué)并得到有效解決。然而有一些問題卻被認(rèn)為很可能不存在有效的(多項(xiàng)式級(jí)的)算法，這里以對(duì)幾個(gè)例題的剖析，簡(jiǎn)述狀態(tài)壓縮思想及其應(yīng)用。58醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮信息學(xué)發(fā)展勢(shì)頭迅猛，信息學(xué)奧賽的題目來(lái)源遍及各行各業(yè)狀態(tài)壓縮

——預(yù)備知識(shí)作為對(duì)下文的準(zhǔn)備，這里先為使用Pascal的OIers簡(jiǎn)要介紹一下C/C++樣式的位運(yùn)算(bitwiseoperation)。其優(yōu)先級(jí)：not>and>xor>or59醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——預(yù)備知識(shí)作為對(duì)下文的準(zhǔn)備，這里先為使用Pasc狀態(tài)壓縮

——預(yù)備知識(shí)位運(yùn)算的特殊應(yīng)用and：用以取出一個(gè)數(shù)的某些二進(jìn)制位取出一個(gè)數(shù)二進(jìn)制中的最后一個(gè)1(lowbit)：x&-xor：將一個(gè)數(shù)的某些位設(shè)為1not：間接構(gòu)造一些數(shù)：~0u=4294967295=232-1xor：不使用中間變量交換兩個(gè)數(shù)：a=a^b; b=b^a; a=a^b;將一個(gè)數(shù)的某些位取反60醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——預(yù)備知識(shí)位運(yùn)算的特殊應(yīng)用4醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——引例在n*n(n≤20)的方格棋盤上放置n個(gè)車(可以攻擊所在行、列)，求使它們不能互相攻擊的方案總數(shù)。10秒時(shí)間思考61醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——引例在n*n(n≤20)的方格棋盤上放置n個(gè)車狀態(tài)壓縮

——引例這個(gè)題目之所以是作為引例而不是例題，是因?yàn)樗鼘?shí)在是個(gè)非常簡(jiǎn)單的組合學(xué)問題我們一行一行放置，則第一行有n種選擇，第二行n-1，……，最后一行只有1種選擇，根據(jù)乘法原理，答案就是n!這里既然以它作為狀態(tài)壓縮的引例，當(dāng)然不會(huì)是為了介紹組合數(shù)學(xué)。我們下面來(lái)看另外一種解法：狀態(tài)壓縮遞推(StatesCompressingRecursion,SCR)62醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——引例這個(gè)題目之所以是作為引例而不是例題，是因?yàn)闋顟B(tài)壓縮

——引例解法我們?nèi)匀灰恍幸恍蟹胖?。取棋子的放置情況作為狀態(tài)，某一列如果已經(jīng)放置棋子則為1，否則為0。這樣，一個(gè)狀態(tài)就可以用一個(gè)最多20位的二進(jìn)制數(shù)表示。例如n=5,第1、3、4列已經(jīng)放置，則這個(gè)狀態(tài)可以表示為01101(從右到左)。設(shè)fs為達(dá)到狀態(tài)s的方案數(shù)，則可以嘗試建立f的遞推關(guān)系。63醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——引例解法我們?nèi)匀灰恍幸恍蟹胖谩?醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——引例解法考慮n=5,s=01101因?yàn)槲覀兪且恍幸恍蟹胖玫?，所以?dāng)達(dá)到s時(shí)已經(jīng)放到了第三行。又因?yàn)橐恍心芮覂H能放置一個(gè)車，所以我們知道狀態(tài)s一定來(lái)自：64醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——引例解法考慮n=5,s=011018醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——引例解法①前兩行在第3、4列放置了棋子(不考慮順序，下同)，第三行在第1列放置；②前兩行在第1、4列放置了棋子，第三行在第3列放置；③前兩行在第1、3列放置了棋子，第三行在第4列放置。65醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——引例解法①前兩行在第3、4列放置了棋子(不考慮狀態(tài)壓縮

——引例解法這三種情況互不相交，且只可能有這三種情況，根據(jù)加法原理，fs應(yīng)該等于這三種情況的和。寫成遞推式就是：66醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——引例解法這三種情況互不相交，且只可能有這三種情狀態(tài)壓縮

——引例解法根據(jù)上面的討論思路推廣之，得到引例的解決辦法：其中s的右起第i+1位為1(其實(shí)就是在枚舉s的二進(jìn)制表示中的1)67醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——引例解法根據(jù)上面的討論思路推廣之，得到引例的解狀態(tài)壓縮

——引例的實(shí)現(xiàn)ProgP0{ read(n); int64f[1..220]={0}; f[0]=1; for(inti=1;i<2n;i++) for(intt=i;t>0;t-=t&-t) f[i]+=f[i^(t&-t)]; write(f[2n-1]);}68醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——引例的實(shí)現(xiàn)ProgP012醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——對(duì)引例的思考反思這個(gè)算法，其正確性毋庸置疑(可以和n!對(duì)比驗(yàn)證)但是算法的時(shí)間復(fù)雜度為O(n2n)，空間復(fù)雜度O(2n)，是個(gè)指數(shù)級(jí)的算法，比循環(huán)計(jì)算n!差了好多，它有什么優(yōu)勢(shì)？（還有一個(gè)很…的用處，即對(duì)新手說(shuō)：“來(lái)看看我這個(gè)計(jì)算n!的程序，連這都看不懂就別OI了~”）可擴(kuò)展性??！69醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——對(duì)引例的思考反思這個(gè)算法，其正確性毋庸置疑(可狀態(tài)壓縮

——例1在n*n(n≤20)的方格棋盤上放置n個(gè)車，某些格子不能放，求使它們不能互相攻擊的方案總數(shù)。30s思考時(shí)間70醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例1在n*n(n≤20)的方格棋盤上放置n個(gè)車狀態(tài)壓縮

——例1分析對(duì)于這個(gè)題目，如果組合數(shù)學(xué)學(xué)得不夠扎實(shí)，應(yīng)該很難一眼看出解法。本題確實(shí)存在數(shù)學(xué)方法(容斥原理)，但因?yàn)楹鸵瑯拥睦碛?，這里不再贅述。引例的算法是在枚舉當(dāng)前行(即s中1的個(gè)數(shù)，設(shè)為r)的放置位置(即枚舉每個(gè)1)而對(duì)于例1，第r行可能存在無(wú)法放置的格子，怎么解決？枚舉1的時(shí)候判斷一下嘛！71醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例1分析對(duì)于這個(gè)題目，如果組合數(shù)學(xué)學(xué)得不夠扎實(shí)狀態(tài)壓縮

——例1解法事實(shí)上，我們并不需要對(duì)引例的算法進(jìn)行太大的改變，只要在枚舉s中的1的時(shí)候判斷一下是否是不允許放置的格子即可然而對(duì)于n=20，O(n2n)的復(fù)雜度已經(jīng)不允許我們?cè)龠M(jìn)行多余的判斷。所以實(shí)現(xiàn)這個(gè)算法時(shí)應(yīng)該應(yīng)用一些技巧。我們用ar表示第r行不允許放置的情況，如果第r行某一位不允許放置則ar此位為0，否則為1，這可以在讀入數(shù)據(jù)階段完成72醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例1解法事實(shí)上，我們并不需要對(duì)引例的算法進(jìn)行太狀態(tài)壓縮

——例1解法然后對(duì)于需要處理的狀態(tài)s，用ts=s&ar來(lái)代替s進(jìn)行枚舉，即不枚舉s中的1轉(zhuǎn)而枚舉ts中的1。因?yàn)閠s保證了不允許放置的位為0，這樣就可以不用其它的判斷來(lái)實(shí)現(xiàn)算法代碼中只增加了計(jì)算a數(shù)組和r的部分，而時(shí)間復(fù)雜度沒有變化。73醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例1解法然后對(duì)于需要處理的狀態(tài)s，用ts=s&狀態(tài)壓縮

——對(duì)例1的思考我們直接套用引例的算法就使得看上去更難的例1得到了解決。雖然這題用容斥原理更快，但容斥原理在這題上只有當(dāng)棋盤為正方形、放入的棋子個(gè)數(shù)為n、且棋盤上禁止放置的格子較少時(shí)才有較簡(jiǎn)單的形式和較快的速度。如果再對(duì)例1進(jìn)行推廣，要在m*n的棋盤上放置k個(gè)車，那么容斥原理是無(wú)能為力的，而SCR算法只要進(jìn)行很少的改變就可以解決問題。這也體現(xiàn)出了引例中給出的算法的擴(kuò)展?jié)摿Α?4醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——對(duì)例1的思考我們直接套用引例的算法就使得看上去狀態(tài)壓縮

——例2有一個(gè)n*m的棋盤(n、m≤80,n*m≤80)要在棋盤上放k(k≤20)個(gè)棋子，使得任意兩個(gè)棋子不相鄰。求合法的方案總數(shù)5min思考、討論、提問時(shí)間75醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例2有一個(gè)n*m的棋盤(n、m≤80,n*m≤狀態(tài)壓縮

——例2分析觀察題目給出的規(guī)模，n、m≤80，這個(gè)規(guī)模要想用SC是困難的，280無(wú)論在時(shí)間還是空間上都無(wú)法承受然而我們還看到n*m≤80稍微思考我們可以發(fā)現(xiàn)：9*9=81>80，即如果n,m都大于等于9，將不再滿足n*m≤80這一條件。所以，我們有n或m小于等于8，而28是可以承受的！76醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例2分析觀察題目給出的規(guī)模，n、m≤80，這個(gè)狀態(tài)壓縮

——例2分析我們假設(shè)m≤n，n是行數(shù)m是列數(shù)，則每行的狀態(tài)可以用m位的二進(jìn)制數(shù)表示但是本題和例1又有不同：例1每行每列都只能放置一個(gè)棋子，而本題卻只限制每行每列的棋子不相鄰上例中枚舉當(dāng)前行的放置方案的做法依然可行。我們用數(shù)組s保存一行中所有的num個(gè)放置方案，則s數(shù)組可以在預(yù)處理過程中用DFS求出，同時(shí)用ci保存第i個(gè)狀態(tài)中1的個(gè)數(shù)以避免重復(fù)計(jì)算77醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例2分析我們假設(shè)m≤n，n是行數(shù)m是列數(shù)，則每狀態(tài)壓縮

——例2分析開始設(shè)計(jì)狀態(tài)。本題狀態(tài)的維數(shù)需要增加，原因在于并不是每一行只放一個(gè)棋子，也不是每一行都要求有棋子，原先的表示方法已經(jīng)無(wú)法完整表達(dá)一個(gè)狀態(tài)。我們用fi,j,k表示第i行的狀態(tài)為sj且前i行總共放置k個(gè)棋子（下面用pn代替原題中的k）的方案數(shù)。沿用枚舉當(dāng)前行方案的做法，只要當(dāng)前行的放置方案和上一行的不沖突。微觀地講，就是要兩行的狀態(tài)s1和s2中沒有同為1的位即可，亦即s1&s2=078醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例2分析開始設(shè)計(jì)狀態(tài)。本題狀態(tài)的維數(shù)需要增加，狀態(tài)壓縮

——例2解法然而，雖然我們枚舉了第i行的放置方案，但卻不知道其上一行(第i-1行)的方案為了解決這個(gè)問題，我們不得不連第i-1行的狀態(tài)一起枚舉，則可以寫出遞推式：其中s1=0，即在當(dāng)前行不放置棋子；j和p是需要枚舉的兩個(gè)狀態(tài)編號(hào)。79醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例2解法然而，雖然我們枚舉了第i行的放置方案，狀態(tài)壓縮

——例2解法本題至此基本解決。當(dāng)然，實(shí)現(xiàn)上仍有少許優(yōu)化空間，例如第i行只和第i-1行有關(guān)，可以用滾動(dòng)數(shù)組節(jié)省空間。這個(gè)算法時(shí)間復(fù)雜度O(n*pn*num2)，空間復(fù)雜度(滾動(dòng)數(shù)組)O(pn*num)運(yùn)用簡(jiǎn)單的組合數(shù)學(xué)知識(shí)可以求出本題中的num=144，因而對(duì)于本題的數(shù)據(jù)規(guī)?？梢院芸斐鼋?0醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例2解法本題至此基本解決。當(dāng)然，實(shí)現(xiàn)上仍有少許狀態(tài)壓縮

——例3給出一個(gè)n*m(n≤100,m≤10)的棋盤，一些格子不能放置棋子。求最多能在棋盤上放置多少個(gè)棋子，使得每一行每一列的任兩個(gè)棋子間至少有兩個(gè)空格。題目來(lái)源：NOI2001《炮兵陣地》TOI1023；POJ118530s思考時(shí)間81醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例3給出一個(gè)n*m(n≤100,m≤10)的棋狀態(tài)壓縮

——例3分析仍然先用DFS搜出一行可能狀態(tài)s，依舊用c[]保存s[]中1的個(gè)數(shù)，依照例1的預(yù)處理搞定不能放置棋子的格子（應(yīng)該有這種意識(shí)）問題是，這個(gè)題目的狀態(tài)怎么選？繼續(xù)像例2那樣似乎不行，原因在于棋子的攻擊范圍加大了82醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例3分析仍然先用DFS搜出一行可能狀態(tài)s，依舊狀態(tài)壓縮

——例3分析但是我們照葫蘆畫瓢：例2的攻擊范圍只有一格，所以我們的狀態(tài)中只需要有當(dāng)前行的狀態(tài)，再枚舉上一行的狀態(tài)即可進(jìn)行遞推；而本題攻擊范圍是兩格，因此增加一維來(lái)表示上一行的狀態(tài)。83醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例3分析但是我們照葫蘆畫瓢：例2的攻擊范圍只有狀態(tài)壓縮

——例3解法用fi,j,k表示第i行狀態(tài)為sj、第i-1行狀態(tài)為sk時(shí)前i行至多能放置的棋子數(shù)。則狀態(tài)轉(zhuǎn)移方程很容易寫出：顯然，算法時(shí)間復(fù)雜度為O(n*num3)，空間復(fù)雜度(滾動(dòng)數(shù)組)O(num2)因?yàn)槠遄庸舴秶鸀閮筛?，可以直觀地想像到本題的num不會(huì)很大。的確，可以算出本題num≤60。84醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例3解法用fi,j,k表示第i行狀態(tài)為sj、第狀態(tài)壓縮

——例3題外話此算法還有優(yōu)化空間我們分別枚舉了三行的狀態(tài)，還需要對(duì)這三個(gè)狀態(tài)進(jìn)行是否沖突的判斷，這勢(shì)必會(huì)重復(fù)枚舉到一些沖突的狀態(tài)組合在DFS出s[]后，我們可以算出哪些狀態(tài)對(duì)可以分別作為兩行的狀態(tài)，這樣在DP時(shí)就不需要進(jìn)行盲目的枚舉，理論上效率會(huì)更高。但因?yàn)閚um本身很小，所以這樣修改沒有顯著地減少運(yùn)行時(shí)間85醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例3題外話此算法還有優(yōu)化空間29醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例3題外話值得一提的是，本題筆者的算法雖然在理論上并不是最優(yōu)（有種應(yīng)用三進(jìn)制的方法），但由于位運(yùn)算的使用，截至07年8月17日，筆者的程序在PKUOJ上長(zhǎng)度最短，速度第二快。但是很不幸，公元2007年8月18日，天津大學(xué)06級(jí)的某同學(xué)去掉本算法的一些關(guān)鍵判斷，達(dá)到了更短的長(zhǎng)度，但其速度慢了3倍……86醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例3題外話值得一提的是，本題筆者的算法雖然在理狀態(tài)壓縮

——例3題外話這個(gè)題目是國(guó)內(nèi)比賽中較早出現(xiàn)的狀態(tài)壓縮題。它告訴我們狀態(tài)壓縮不僅可以像前幾個(gè)例題那樣求方案數(shù)，而且可以求最優(yōu)方案，即狀態(tài)壓縮思想既可以應(yīng)用到遞推上(SCR)，又可以應(yīng)用到DP上(SCDP)，更說(shuō)明其有廣泛的應(yīng)用空間。87醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例3題外話這個(gè)題目是國(guó)內(nèi)比賽中較早出現(xiàn)的狀態(tài)壓狀態(tài)壓縮

——新的模型看了這么多棋盤模型應(yīng)用狀態(tài)壓縮的實(shí)例，可能會(huì)讓人產(chǎn)生錯(cuò)覺，以為狀態(tài)壓縮只在棋盤上放棋子的題目中有用。我們暫時(shí)轉(zhuǎn)移視線，來(lái)看看狀態(tài)壓縮在其他地方的應(yīng)用——覆蓋模型。88醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——新的模型看了這么多棋盤模型應(yīng)用狀態(tài)壓縮的實(shí)例，狀態(tài)壓縮

——例4給出n*m(1≤n、m≤11)的方格棋盤，用1*2的長(zhǎng)方形骨牌不重疊地覆蓋這個(gè)棋盤，求覆蓋滿的方案數(shù)。。經(jīng)典問題TOJ1343;POJ2411Haveabreak!89醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例4給出n*m(1≤n、m≤11)的方格棋盤，狀態(tài)壓縮

——例4背景這也是個(gè)經(jīng)典的組合數(shù)學(xué)問題：多米諾骨牌完美覆蓋問題(或所謂二聚物問題)。有很多關(guān)于這個(gè)問題的結(jié)論，甚至還有個(gè)專門的公式:誰(shuí)看得懂、記得??？？？90醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例4背景這也是個(gè)經(jīng)典的組合數(shù)學(xué)問題：多米諾骨牌狀態(tài)壓縮

——例4分析顯然，如果n、m都是奇數(shù)則無(wú)解(由棋盤面積的奇偶性知)，否則必然有至少一個(gè)解(很容易構(gòu)造出)因此假設(shè)n、m至少有一個(gè)偶數(shù)，且m≤n我們依然像前面的例題一樣把每行的放置方案DFS出來(lái)，逐行計(jì)算91醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例4分析顯然，如果n、m都是奇數(shù)則無(wú)解(由棋盤狀態(tài)壓縮

——例4解法用fi,s表示把前i-1行覆蓋滿、第i行覆蓋狀態(tài)為s的覆蓋方案數(shù)因?yàn)樵诘趇行上放置的骨牌最多也只能影響到第i-1行，則容易得遞推式：92醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例4解法用fi,s表示把前i-1行覆蓋滿、第i狀態(tài)壓縮

——例4細(xì)節(jié)首先討論DFS的一些細(xì)節(jié)。對(duì)于當(dāng)前行每一個(gè)位置，我們有3種放置方法：①豎直覆蓋，占據(jù)當(dāng)前格和上一行同一列的格；②水平覆蓋，占據(jù)當(dāng)前格和該行下一格；③不放置骨牌，直接空格。如何根據(jù)這些枚舉出每個(gè)(s1,s2)呢？下面介紹兩種方法。93醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例4細(xì)節(jié)首先討論DFS的一些細(xì)節(jié)。37醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例4DFS方法1DFS共5個(gè)參數(shù)，分別為：p(當(dāng)前列號(hào))，s1、s2(當(dāng)前行和上一行的覆蓋情況)，b1、b2(上一列的放置對(duì)當(dāng)前列兩行的影響，影響為1否則為0)。初始時(shí)s1=s2=b1=b2=0。①p=p+1，s1=s1*2+1，s2=s2*2（注意：第i行的放置方案用到第i-1行的某格時(shí)，s2中該格應(yīng)為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。當(dāng)p移出邊界且b1=b2=0時(shí)記錄此方案。94醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例4DFS方法1DFS共5個(gè)參數(shù)，分別為：p狀態(tài)壓縮

——例4DFS方法2觀察第一種方法，發(fā)現(xiàn)b2始終為0，知這種方法有一定的冗余。換個(gè)更自然的方法，去掉參數(shù)b1、b2。①p=p+1，s1=s1*2+1，s2=s2*2；②p=p+2，s1=s1*4+3，s2=s2*4+3；③p=p+1，s1=s1*2，s2=s2*2+1。當(dāng)p移出邊界時(shí)記錄此方案。這樣，我們通過改變p的移動(dòng)距離成功簡(jiǎn)化了DFS過程，而且這種方法更加自然。95醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例4DFS方法2觀察第一種方法，發(fā)現(xiàn)b2始終狀態(tài)壓縮

——例4細(xì)節(jié)DFS過程有了，實(shí)現(xiàn)方法卻還有值得討論的地方前面的例題中，我們?yōu)槭裁纯偸前逊胖梅桨窪FS預(yù)處理保存起來(lái)？是因?yàn)椴缓戏ǖ臓顟B(tài)太多，每次都重新DFS太浪費(fèi)時(shí)間。然而回到這個(gè)題目，特別是當(dāng)采用第二種時(shí)，我們的DFS過程中甚至只有一個(gè)判斷(遞歸邊界)，說(shuō)明根本沒有多少不合法的方案，也就沒有必要把所有方案保存下來(lái)，對(duì)于每行都重新DFS即可96醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例4細(xì)節(jié)DFS過程有了，實(shí)現(xiàn)方法卻還有值得討狀態(tài)壓縮

——例4細(xì)節(jié)這個(gè)算法時(shí)間復(fù)雜度為多少呢？因?yàn)镈FS時(shí)以兩行為對(duì)象，每行2m，共進(jìn)行n次DFS，所以是O(n*4m)？這會(huì)使人誤以為本算法無(wú)法通過1≤n、m≤11的測(cè)試數(shù)據(jù)，而實(shí)際上本算法可以瞬間給出m=10,n=11時(shí)的解為了計(jì)算精確的復(fù)雜度，必須先算出DFS得到的方案數(shù)。97醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例4細(xì)節(jié)這個(gè)算法時(shí)間復(fù)雜度為多少呢？因?yàn)镈F狀態(tài)壓縮

——例4復(fù)雜度分析考慮當(dāng)前行的放置情況。如果每格只有①③兩個(gè)選擇，則應(yīng)該有2m種放置方案；如果每格有①②③這3個(gè)選擇，且②中p只移動(dòng)一格，則應(yīng)該有3m種放置方案。然而現(xiàn)在的事實(shí)是：每格有①②③這3個(gè)選擇，但②中p移動(dòng)2格，所以可以知道方案數(shù)應(yīng)該在2m和3m之間98醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例4復(fù)雜度分析考慮當(dāng)前行的放置情況。42醫(yī)藥狀態(tài)壓縮

——例4復(fù)雜度分析考慮第i列，則其必然是：第i-1列采用①③達(dá)到；第i-2列采用②達(dá)到。設(shè)hi表示前i列的方案數(shù)，則得到hi的計(jì)算式：99醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例4復(fù)雜度分析考慮第i列，則其必然是：43醫(yī)狀態(tài)壓縮

——例4復(fù)雜度分析注意到式子的第二項(xiàng)是多個(gè)絕對(duì)值小于1的數(shù)的乘積，其對(duì)整個(gè)hm的影響甚小，故略去，得到方案數(shù)hm≈0.85*2.414m，符合2m<hm<3m的預(yù)想。因?yàn)榭偣策M(jìn)行了n次DFS，每次復(fù)雜度為O(hm)，所以算法總時(shí)間復(fù)雜度為O(n*hm)=O(n*0.85*2.414m)，對(duì)m=10,n=11不超時(shí)也就不足為奇了。應(yīng)用滾動(dòng)數(shù)組，空間復(fù)雜度為O(2m)。100醫(yī)藥醫(yī)學(xué)狀態(tài)壓縮

——例4復(fù)雜度分析注意到式子的第二項(xiàng)是多個(gè)絕對(duì)值狀態(tài)壓縮

——例5給出n*m(1≤n、m≤9)的方格棋盤，用1*2的矩形的骨牌