POJ 2411 Mondriaan's Dream 状态压缩 动态规划

题目描述:
给出一个 h*w 的空棋盘,1<=h,w<=11,若用1*2或2*1的骨牌去完全覆盖这个棋盘,问有多少种方法?

题目分析:
      规模很小,棋盘的每个格子有覆盖和未覆盖两种,正好对应二进制中的 1 和 0 。所以可以用一个二进制数表示一行棋盘的状态,这称之为状态压缩,然后对其进行相应的位运算,表示相应的操作。

     首先,我们明确一下状态的在该题的意义: 若当前格被一个1*2的骨牌盖住,或者被一个2*1的骨牌下面格盖住,则为 1 ;否则为0 。
     有了状态,我们就可以得出一些结论:
     1.当前行的状态只与上一行有关;
     2.若上行某个为0,则下行相应格必须为1;若上行某格为1,则下行相应格可为 0 或1;
     这样我们就可以有上一行的状态,递推出下一行的状态了。我们可以先求出所有的用1*2骨牌填一列的状态集M。然后,用每一个状态A去与上行状态判断,若有矛盾,则证明当前行不能为A;否则,A状态的方法数可由上行得出。
      用一个方程表示: F[ row  , i ] = sum ( f[row - 1 , j ] )  , j表示上行状态,i表示与j无矛盾的状态。
参考程序:

 

posted on 2010-08-19 17:21 IronOxide 阅读(738) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年8月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

导航

统计

常用链接

留言簿

随笔分类

随笔档案

ACMer

方向

搜索

最新评论

阅读排行榜

评论排行榜