编程兔暑假3.5阶段集训Day6——状压（状态压缩）dp、dp优化以及图论

        今天我们先来讲一下状态压缩dp（也称状压dp）。状压dp，顾名思义，就是把状态压缩起来。比如对于8*8 的棋盘，每个位置可以放一个棋子，对于在第i行第2个位置和第6个位置放了棋子，我们可能需要8维或9维数组表示。因此我们就有了把一行状态压缩成一个数字的做法。一般我们会转化为二进制，如果每个位置可以有3种状态，那我们可以采用三进制。这样只需要一个大小为2^8的一维数组我们就可以存下所有状态，这就是状态压缩。

eg1
• 现在有 n*m 的方格棋盘，和无限的 1*2 的骨牌，问有多少种方法能用骨牌 铺满棋盘。
• 1<=n,m<=11.

算法分析：
首先 n*m 是奇数一定拼不出来。使用状态压缩，如果第 i 个位置上放骨牌，就在二进制对应位置填 1，否则是 0. 用 f[i][s] 表示填到了第 i 行状态是 s 的方案数。答案就是 f[n][(1<<m)-1]。可是怎样进行状态的转移呢？
首先我们的决策有两种：横着放或者竖着放。
我们需要连续考虑二行，如果横着放，需要两个连续的空位，且上一行这两个位置也被覆盖；如果竖着放有2种情况：
    1、上一行位置是空的，我们就可以把空填上。
    2、上一行是覆盖的，那么我们把这一行位置设为空，表示下一行必须竖着放 填上这块空白。

代码实现：
void dfs(int i,int now,int pre)
{
	if(i>m)
	{
		return ;
	}
	if(i==m)
	{
		++tot;
		from[tot]=pre;
		to[tot]=now;
		return ;
	}
	dfs(i+2,now<<2|3,pre<<2|3);
	dfs(i+1,now<<1,(pre<<1)|1);
	dfs(i+1,now<<1|1,pre<<1);
}

主函数： 
int f[12][1<<11];
dfs(0,0,0);
f[0][(1<<m)-1]=1;
for(int i=0;i<n;i++)
{
	for(int j=1;j<=tot;j++)
	{
		f[i+1][to[j]]+=f[i][from[j]];
	}
}