动态规划专辑——状态压缩

状态压缩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.《状态压缩》——周伟