POJ 2411 Mondriaan's Dream （dp + 狀態壓縮）
題意：題目描述：用1*2 的矩形通過組合拼成大矩形，求拼成指定的大矩形有幾種拼法。
思路：我看了上面的博客，想了很久才明白是如何處理狀態的。
由於是1 * 2，所以可以通過相鄰兩行的轉化關系來推導。
兩行鋪不鋪磚可以用二進制來表示，但是如果暴力枚舉，大概有2^10 * 2 ^ 10 次那麼多狀態（雖然其中有很多狀態是沒有用的）。
所以采用dfs來枚舉各種可行狀態：
狀態標記 橫放和豎放的下一個均為1，豎放的上一個和不放置為0 ，每行可以轉化為1個2進制數。當這一行訪問結束時，就會得到上一行狀態，和該行狀態，因為所有情況都是我們設置的，所以pre狀態一定會轉化為now狀態
對於每一個位置，我們有三種放置方法：1. 豎直放置2. 水平放置3. 不放置
d為當前列號 ，初始化d, now, pre都為0。now為當前行，pre為當前行的上一行
1. d = d + 1, now << 1 | 1, pre << 1; // 豎直放置，當前行該列為1，上一行該列置為0
2. d = d + 2, now << 2 | 3, pre<< 2 | 3; // 橫放 都為11（因為當兩行的狀態往下推時，必須要保證pre這一行擺滿，所以pre也都為11）
3. d = d + 1, now << 1, pre<< 1 | 1; // 上一行該列置為1，不能豎放，不放置的狀態
因為轉移狀態有很多種，所以用dfs去枚舉各種可行的狀態。
最後在轉移的時候，dp[0][(1 << w) - 1] = 1 表示只有第0行全部鋪滿才行。只需要算到 h - 1 行，然後 h 行全部鋪滿為答案。
代碼：
/*
ID: [email protected]
PROG:
LANG: C++
*/
#include
