動态規劃專輯——狀态壓縮

狀态壓縮DP

預備知識：位運算！

位運算講稿 byMatrix67

注意：位運算的優先級非常低，用的時候一定要注意多加括号！

1.棋盤模型：給一個棋盤，問滿足要求的棋子放置方案數或最多放置數

1.sgu220TODO：littlebishop ：攻擊範圍：對角線的4個點，SCR

2.sgu221TODO：bigBishop: 棋盤多項式

3.sgu222：n*n的棋盤，放k個車，使他們不能互相攻擊，問有多少種放法。

定義狀态S表示每列的放置情況，S為n位的二進制數，第i位為1表示第i列放棋子，為0表示不放棋子。

F[i][S]:前i行，列的狀态為S的方案數

F[i][S]=Sum(F[i-1][S],F[i-1][S-2^j])/每行至多放一個，目前行放置在第j個。

ans=sum(F[n][s]), 其中S中有k個1

複雜度O（N^2*2^N)

補充：本題有組合數學方法，C（N，K）*A（N，K）但不是講這題的目的。。。

4.sgu 223 n*n的棋盤，放k個國王，使他們不能互相攻擊，問有多少種放法。（國王攻擊範圍為他周圍的8個點）

這題因為不滿足每行隻放一個的條件，是以不能像上一題那樣解決。而且求解目前行，和上一行的狀态有關，是以狀态轉移的時候需要上行的狀态。

F[i][S][j]:前i行放j個國王，第i行狀态為S的方案數。

F[i][S][j]=sum(F[i-1][S'][j-Count(S)])S和S‘不沖突，Count（S）表示S中1的個數。

ans=Sum(F[i][S][K])

複雜度分析

狀态數：N*2^N*K(N^2)=N^3*2^N,轉移代價2^N

時間優化（減少狀态數）：

每行的狀态S不必要從0到2^N-1枚舉，因為有些狀态行内就沖突了！

補充：格子數為m的一行放棋子，相鄰兩個棋子中間的空格數不少于d的狀态數：

Num=C(m,0)+C(m,1)+C(m-d,2)+C(m-2d,3)+......

可以dfs預處理出所有可行的狀态，把可行的狀态儲存起來，本題的可行狀态數大約減少為200個。總複雜度約為4*10^7

空間優化：滾動數組！

如何判斷S和S‘沖突。

（S<<1）&S'==0，S&S’==0，(S>>1)& S' ==0

5.POJ3254 求方案數，類似上題

6.POJ1185求最大放的個數

7.hdu4539TODO炮兵陣地：曼哈頓距離版

2.鋪磚/覆寫模型：

1.poj24111*2多米諾骨牌覆寫n*m的棋盤方案數。

公式（生成函數）：mul(1-m/2)mul(1-n/2)[4cos^2(iPi/(m+1)+4cos^2(jPi/(n+1)) ]

狀态壓縮

Reference

1.位運算講稿by Matrix67

2.《狀态壓縮》——周偉