编程兔暑假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优化以及图论
地址分享:http://scyanting.com/article/dsoigjd.html