POJ 2411 Mondriaans Dream （狀態壓縮DP）

題意：給定一個矩陣，只能放1*2的木塊，問將這個矩陣完全覆蓋的不同放法有多少種。

分析：橫著放為11，豎著放為豎著的01，所以判斷相鄰兩行是否被完全覆蓋：只需判斷兩行狀態合集（j | k）是否是滿的, 兩種狀態是否有沖突（j & k）。

第一行直接預處理就行。

#include <cstdio>   
#include <iostream>   
#include <cstring>   
#include <algorithm>   
using namespace std;  
__int64 dp[12][1 << 11]; //橫著放為11，豎著放為0   
                       //                    1   
int buff[1 << 11];  
int n,m;  
__int64 ans;  
  
bool judge(int b) {  
    bool flag = 1;  
    while(b) {  
        if(b & 1) {  
            if((b >> 1) & 1) b = b >> 2;  
            else {  
                flag = 0;  
                b = b >> 1;  
            }  
        } else b = b >> 1;  
        if(flag == 0) return 0;  
    }  
    return flag;  
}  
void getbuff() {  
    int total = 1 << 11;  
    for(int i=0; i<total; i++) {  
        if(judge(i)) {  
            buff[i] = 1;  
        }  
    }  
}  
  
void solve() {  
    int total = 1 << m;  
    for(int i=1; i<n; i++) { //最後一行一定全是1   
        for(int j=0; j<total; j++) {  
            for(int k=0; k<total; k++) {  
                if((j | k) == total-1 && buff[(j & k)]) {  
                    dp[i][j] += dp[i-1][k];  
                }  
            }  
        }  
    }  
    ans = dp[n-1][total-1];  
}  
  
int main() {  
    getbuff();  
    while(scanf("%d%d",&n,&m) ) {  
        if(n == 0 && m == 0 ) break;  
        if(n == 1) {  
            if(m % 2 == 0) printf("1\n");  
            else printf("0\n");  
            continue;  
        }  
        int total = 1 << m;  
        memset(dp,0,sizeof(dp));  
        for(int i=0; i<total; i++) {  
            if(buff[i]) dp[0][i] = 1;  
        }  
        ans = 0;  
        solve();  
        printf("%I64d\n",ans);  
    }  
    return 0;  
}