[cpp]?
/*
正常求解超时，然后打表通过。
自己定义状态，我的解法横木块[0,0]，竖木块[1,0]，其中1表示下层。
也可以横木块[0,0]，竖木块[1,2]，不过会多出一个状态，需要3进制表示。
*/?
?
//打表程序?
#include ?
#include ?
__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 ?
__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;?
}?
|