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

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

成都创新互联是一家专业提供宽甸企业网站建设,专注与成都网站制作、成都网站建设、外贸营销网站建设、H5开发、小程序制作等业务。10年已为宽甸众多企业、政府机构等服务。创新互联专业网站建设公司优惠进行中。

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

算法分析：
首先 n*m 是奇数一定拼不出来。使用状态压缩，如果第 i 个位置上放骨牌，就在二进制对应位置填 1，否则是 0. 用 f[i][s] 表示填到了第 i 行状态是 s 的方案数。答案就是 f[n][(1<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<            
            
                        

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

            URL分享：http://cdkjz.cn/article/dsoigjd.html