POJ 2411 Mondriaans Dream(狀態壓縮)

[cpp] 
/*
正常求解超時，然後打表通過。
自己定義狀態，我的解法橫木塊[0,0]，豎木塊[1,0]，其中1表示下層。
也可以橫木塊[0,0]，豎木塊[1,2]，不過會多出一個狀態，需要3進制表示。
*/ 
 
//打表程序 
#include <cstdio> 
#include <cstring> 
__int64 h, w; 
__int64 d[11][1 << 11]; 
 
__int64 check1(__int64 x)//相連的0必須為偶數個 
{ 
    __int64 i; 
    __int64 z = 0; 
    for(i = 0; i < w; ++ i) 
    { 
        if(x & (1 << i)) 
        { 
            if(z % 2 != 0) return 0; 
            z = 0; 
        } 
        else 
            z ++; 
    } 
    if(z % 2 != 0) return 0; 
    return 1; 
} 
 
__int64 check2(__int64 x, __int64 y)//判斷前後兩個狀態x,y是否符合條件 
{ 
    if(x & y) return 0; 
    __int64 tmp = x | y; 
    return check1(tmp); 
} 
 
__int64 max(__int64 a, __int64 b) 
{ 
    return a > b ? a : b; 
} 
int main() 
{ 
    freopen("e://data.out", "w", stdout); 
    for(h = 1; h <= 11; ++ h) 
        for(w = 1; w <= 11; ++ w) 
    { 
        __int64 up = (1 << w); 
        __int64 i, j, k; 
        memset(d, 0, sizeof(d)); 
        for(i = 0; i < h; ++ i) 
        { 
            for(j = 0; j < up; ++ j) 
            { 
                if(i == 0) 
                { 
                    if(!check1(j)) continue; 
                    d[i][j] = 1; 
                } 
                else 
                { 
                    for(k = 0; k < up; ++ k) 
                    { 
                        if(check2(j, k)) 
                        { 
                            d[i][j] += d[i - 1][k]; 
                        } 
                    } 
                } 
            } 
        } 
        printf("%I64d,", d[h - 1][0]); 
    } 
    return 0; 
} 
 
 
//主程序 
#include <cstdio> 
__int64 A[]={0,1,0,1,0,1,0,1,0,1,0,1,2,3,5,8,13,21,34,55,89,144,0,3,0,11,0,41,0,153,0,571,0,1,5,11,36,95,281,781,2245,6336,18061,51205,0,8,0,95,0,1183,0,14824,0,185921,0,1,13,41,281,1183,6728,31529,167089,817991,4213133,21001799,0,21,0,781,0,31529,0,1292697,0,53175517,0,1,34,153,2245,14824,167089,1292697,12988816,108435745,1031151241,8940739824,0,55,0,6336,0,817991,0,108435745,0,14479521761,0,1,89,571,18061,185921,4213133,53175517,1031151241,14479521761,258584046368,3852472573499,0,144,0,51205,0,21001799,0,8940739824,0,3852472573499,0}; 
int main()  www.2cto.com
{ 
    int h, w; 
    while(scanf("%d%d", &h, &w) != EOF) 
    { 
        if(!h && !w) break; 
        h --; 
        w --; 
        printf("%I64d\n", A[h * 11 + w]); 
    } 
    return 0; 
}