pojPOJ 2411--Mondriaan39;s Dream+狀態壓縮dp

pojPOJ 2411--Mondriaan39;s Dream+狀態壓縮dp

又是一道經典的狀態壓縮dp

開始自己想了一下，總是覺得因為這個小矩形可以豎著放導致沒法確定狀態如何轉移(第i行的小矩形如果豎著放,及可能影響i-1行,也有可能影響i+1行);後面看了別人的題解後，才知道原來我們可以固定小矩形豎著放的時候只能向前放，這樣第i行的狀態就只能影響i-1行了，也就能順利的寫出狀態轉移方程啦。

設dp[i][j]表示第i行處於狀態j的時候，共有多少種放置方法。

dp[i][j]=sum(dp[i-1][k]),其中狀態j和k要能共存,並且j和k要使得第i-1行剛好鋪滿。

然後就是初始化，初始化時我們將第一行有連續偶數個1的狀態賦值為1(因為第一行沒有上一行，是不可能出現豎放情況的)其余所有狀態為0。

這個題目中較難處理的就是狀態轉移中j和k必須共存，並且j和k要使得第i-1行剛好鋪滿的這個條件。

代碼中是以j狀態為主然後去判斷k狀態，其實也可以反過來的；具體的處理見代碼。

當然這個題目如果就這樣赤裸裸的交是會超時的，還可以加點優化：

1）如果n*m為奇數，則是不可能拼湊成功的(因為小矩形的面積是偶數)

2) 總是取n,m中小的那個當成m，這樣可以減少狀態總數。

3) 因為n,m很小,輸入的狀態中應該有重復的，所以我們可以把每次的答案記錄下來，下次遇到相同的輸入時直接輸出答案。

還有就是注意一下位運算的優先級(多加括號).

代碼如下：

#include
#include
#include
#include
using namespace std;

long long dp[12][3300];
long long ans[12][3300];
int n,m;

bool init(int x)
{
    for(int i=0;i