Description
Squares and rectangles fascinated the famous Dutch painter Piet Mondriaan. One night, after producing the drawings in his 'toilet series' (where he had to use his toilet paper to draw on, for all of his paper was filled with squares and rectangles), he dreamt of filling a large rectangle with small rectangles of width 2 and height 1 in varying ways.
Expert as he was in this material, he saw at a glance that he'll need a computer to calculate the number of ways to fill the large rectangle whose dimensions were integer values, as well. Help him, so that his dream won't turn into a nightmare!
Input Specification
The input file contains several test cases. Each test case is made up of two integer numbers: the height h and the width w of the large rectangle. Input is terminated by h=w=0. Otherwise, 1<=h,w<=11.
Output Specification
For each test case, output the number of different ways the given rectangle can be filled with small rectangles of size 2 times 1. Assume the given large rectangle is oriented, i.e. count symmetrical tilings multiple times.
Sample Input
Sample Output
Input
Specification
Output
今天集训做这题用怎样的dp都会跪，然后我就自己模拟，还是跪......最后前辈SD指导，原来这是典型的状态压缩问题（所谓状态压缩也弄不懂啥专业术语，就知道针对这题采用的是二进制策略将d[2][][][][][]...后面的m维数组映射为一个2进制的m位，从而用一个d[2][1<<m]的二维数组就搞定啦），下面是对这题我的理解....我是从一点不懂，然后从多段图路径看到轮廓线动态压缩，然后又根据图研究本题的构造方法，最后又理解2进制操作，感觉做ACM的题目好充实，哈哈，加油！！！
本文转自beautifulzzzz博客园博客，原文链接：http://www.cnblogs.com/zjutlitao/p/3525349.html，如需转载请自行联系原作者