随笔-65  评论-6  文章-0  trackbacks-0
 1 #include <iostream>
 2 using namespace std;
 3 typedef __int64 LL;
 4 #define MaxSize 12
 5 LL num[MaxSize][MaxSize];
 6 LL dp[MaxSize][2049];
 7 int h,w,MaxN;
 8 
 9 bool test(int val){
10     int i,sum;
11     for(i=0;i<w;i++){
12         sum=0;
13         while (val & (1<<i))
14             sum++,i++;
15         if(sum & 1)    return false;
16     }
17     return true;
18 }
19 LL getAw(int step,int status){
20     if(step==1){//临界状态
21         if(test(status))    return 1;
22         return 0;
23     }
24     if(dp[step][status]!=-1)
25         return dp[step][status];
26     int i,temp,last=~status;
27     LL sum=0;
28     last &= MaxN;
29     for(i=0;i<=MaxN;i++){
30         if( (i&last) != last)
31             continue;
32         temp=i & status;
33         if(test(temp))
34             sum+=getAw(step-1,i);
35     }
36     dp[step][status]=sum;
37     return sum;
38 }
39 
40 int main(){
41     //freopen("in.txt","r",stdin);
42     memset(num,-1,sizeof(num));
43     while (scanf("%d %d",&h,&w),(h||w)){
44         if(h*w & 1){
45             puts("0");
46             continue;
47         }
48         if(h<w)
49             h^=w,w^=h,h^=w;
50         if(num[h][w]!=-1){
51             printf("%I64d\n",num[h][w]);
52             continue;
53         }
54         int i,j;
55         MaxN=(1<<w)-1;
56         for(i=1;i<=h;i++)
57             for(j=0;j<=MaxN;j++)
58                 dp[i][j]=-1;
59         num[h][w]=num[w][h]=getAw(h,MaxN);
60         printf("%I64d\n",num[h][w]);
61     }
62     return 0;
63 }
posted on 2012-07-14 14:55 Leo.W 阅读(161) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理