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，如需轉載請自行聯系原作者