POJ - 2411 Mondriaan's Dream （狀態壓縮）

POJ - 2411 Mondriaan's Dream （狀態壓縮）

題目大意：要在n * m的網格上面鋪滿1 * 2或者 2 ＊ 1的磚塊，問有多少種鋪放的方式

解題思路：剛開始用了3進制表示每行的狀態,0表示的是2 * 1的磚塊的一部分，1表示的是1 ＊ 2的磚塊的上部分，2表示的是1 ＊ 2的磚塊的下部分，然後像poj－1185炮兵陣地 那題一樣去解決就好了，結果發現狀態太多了，會TLE，只得放棄了
後面參考了下別人的代碼，可以將其轉換成二進制表示形式的，0代表沒該位置沒被鋪到，1代表該位置有被鋪到
因為有1 * 2的這種影響兩行的磚頭存在，所以要判斷兩個狀態能否吻合，只有吻合了才可以
分類討論
1.如果第i行的第j列是1

A.如果第i－1行的第j列也是1，那麼這裡鋪的磚就不可能是1＊2這種類型的磚(影響2行的磚)，也就是他們兩個鋪的都是2*1的磚，那就要判斷其相鄰的那個是不是也是1了，如果不是，就表示兩種狀態不吻合了

B.如果第i－1行的第j列是0，那麼表示第i行第j列的磚是1 ＊ 2的磚，上部分將第i－1行的第j列給鋪了

2.如果第i行的第j列是0

A.如果第i－1行的第j列也是0，那麼就出現空缺了，不符合

B.如果第i－1行的第j列是1，就表示第i行需要第i＋1行鋪1 ＊2的磚來填補了

可參考大神的題解這裡寫鏈接內容
A的代碼

#include
#include
#include
using namespace std;
#define maxn 15
#define maxs (1 << 12)
long long ans[maxn][maxn];
long long dp[maxn][maxs];
int h, m;

bool ok(int s) {
    for(int i = m - 1; i >= 0; i--) {
        if(s & (1 << i)) {
            if(i == 0)
                return false;
            if(!(s & (1 << (i - 1))))
                return false;
            i--;
        }
    }
    return true;
}

bool judge(int s, int ss) {
    for(int i = (m - 1); i >= 0; i--) {
        if(!(ss & (1 << i)) && !(s & (1 << i))) 
            return false;
        if((s & (1 << i))) {
            if(ss & (1 << i)) {
                if(i == 0)
                    return false;
                if(!(s & (1 << (i - 1))) || !(ss & (1 << (i - 1))))
                    return false;
                i--;
            }
        }
    }
    return true;
}

void solve() {
    int t;
    if(h < m) {
        t = h;
        h = m;
        m = t;
    }

    memset(dp, 0, sizeof(dp));
    for(int i = 0; i < (1 << m); i++)
        if(ok(i))
            dp[1][i] = 1;   

    for(int r = 2; r <= h; r++)
        for(int s = 0; s < (1 << m); s++)
            for(int ss = 0; ss < (1 << m); ss++)
                if(judge(s, ss))
                    dp[r][s] += dp[r-1][ss];

    printf(%lld
, ans[h][m] = ans[m][h] = dp[h][(1 << m) - 1]);
}

int main() {
    memset(ans, -1, sizeof(ans));
    while(scanf(%d%d, &h, &m) != EOF && h + m) {
        if(ans[h][m] != -1) {
            printf(%lld
, ans[h][m]);
            continue;
        }
        if((h * m) % 2 == 1) { 
            ans[h][m] = ans[m][h] = 0;
            printf(0
);
            continue;
        }
        solve();
    }
    return 0;
}

三進制超時的代碼

#include
#include
#include
#include
using namespace std;
#define maxn 270000
int state[maxn];
int dp[12][maxn];
int w, h, cnt;
int mod[13];


void init() {

    memset(dp, 0, sizeof(dp));
    cnt = 0;
    bool flag1, flag2;
    for(int i = 0; i < mod[w]; i++) { 
        flag1 = flag2 = false;
        for(int j = w - 1; j >= 0; j--) {
            if((i % mod[j + 1] - i % mod[j]) / mod[j] == 0) {
                if(j == 0) {
                    flag1 = true;
                    break;
                }else {
                    if((i % mod[j] - i % mod[j - 1]) / mod[j - 1] != 0) {
                        flag1 = true;
                        break;
                    }
                }
                j--;
            }
        }

        if(!flag1) {
            for(int j = w - 1; j >= 0; j--) {
                if((i % mod[j + 1] - i % mod[j]) / mod[j] == 2) {
                    flag2 = true;
                    break;
                }
            }
        }
        if(!flag1)
            state[cnt++] = i; 
        if(!flag1 && !flag2)
            dp[0][i] = 1;
    }
}

int solve() {
    for(int r = 1; r < h; r++)
        for(int i = 0; i < cnt; i++)
            for(int j = 0; j < cnt; j++) {
                bool flag = false;
                for(int k = w - 1; k >= 0; k--) {
                    if(((state[j] % mod[k + 1] - state[j] % mod[k] ) / mod[k] == 1) && ( (state[i] % mod[k + 1] - state[i] % mod[k] ) / mod[k] != 2)) {
                        flag = true;
                        break;
                    }
                    if(((state[i] % mod[k + 1] - state[i] % mod[k] ) / mod[k] == 2) && ( (state[j] % mod[k + 1] - state[j] % mod[k] ) / mod[k] != 1)) {
                        flag = true;
                        break;
                    }
                }
                if(!flag) {
                    dp[r][state[i]] += dp[r-1][state[j]];
                }
            }
    int ans = 0;
    for(int i = 0; i < cnt; i++) {
        bool flag = false;
        for(int j = w - 1; j >= 0; j--)
            if((state[i] % mod[j + 1] - state[i] % mod[j]) / mod[j] == 1) {
                flag = true;
                break;
            }
        if(!flag) {
            ans += dp[h - 1][state[i]];
        }
    }
    return ans;
}

void begin() {
    mod[0] = 1;
    for(int i = 1; i < 13; i++)
        mod[i] = mod[i - 1] * 3;
}

int main() {
    begin();
    while(scanf(%d%d, &h, &w) != EOF && h + w) {
        if((h * w) % 2 == 1)
            printf(0
);
        else {
            init();
            printf(%d
, solve());
        }
    }
    return 0;
}