ZJU/ZOJ 1100 Mondriaan's Dream 解题报告

题目大意是求用长为2宽为1的小矩形堆满长为h宽为w的大矩形的方案数。

经典的状态压缩DP例题。用0表示当前位置是横放的小矩形的一部分或是竖放的小矩形的下部，用1表示当前位置是竖放的小矩形的上部。利用位运算和上一行的摆放信息来确定当前位置是否有多种选择，如果有则通过DFS来拓展状态，累加状态计数即可。因为当前一行的摆放只受上一行的限制，所以可以利用滚动数组来优化空间复杂度。注意最后一行只能摆放横放的小矩形，所以在DFS拓展状态时可以加上这一限制避免拓展无效状态。

3023043 2008-08-05 16:39:43 Accepted 1100 FPC 00:00.04 440K IwfWcf