poj2411Mondriaan's Dream<DP>

View Code

 1 #include<cstdio>
 2 #include<string.h>
 3 long long f[2][4100],a,b,n,m,k,j,p;
 4 int main(){
 5    while(scanf("%d%d",&n,&m), n+m){
 6         if( (n*m)&1 ){
 7             puts( "0" );
 8             continue;
 9         }
10         memset(f,0,sizeof(f));
11         f[0][0]=p=1,a=n>m?n:m,b=n+m-a ;
12           for( int i=0; i<a; ++ i ){
13             for(j=0;++j<=b;){
14                 for(k=(1<<b);--k+1;)
15                   if(k&1<<j-1)
16                      f[p][k&~(1<<j-1)]+=f[1-p][k];
17                   else{
18                        f[p][k|1<<j-1]+=f[1-p][k];
19                        if(j<b&&!(k&1<<j))
20                           f[p][k|1<<j]+=f[1-p][k];
21               }
22               memset(f[p=1-p],0,sizeof(f[p]));    
23             }
24           }
25       printf("%lld\n",f[1-p][0]);
26    }
27 }

View Code

 1 #include <iostream>
 2  #include <cstring>
 3  #include <cstdio>
 4  using namespace std;
 5  int n,m;
 6  long long add;
 7  long long dp[2][1<<12];
 8  void dfs(int i,int s,int cur)
 9  {
10      if(cur==m) {dp[i][s]+=add;return;}
11      dfs(i,s,cur+1);
12      if(cur<m-1&&!(s&1<<cur)&&!(s&1<<(cur+1)))
13          dfs(i,s|1<<cur|1<<(cur+1),cur+2);
14  }
15  int main()
16  {
17      while(scanf("%d%d",&n,&m),n+m)
18      {
19          if(n*m%2) {printf("0\n");continue;}
20          int rt=(1<<m)-1;
21          add=1;
22          memset(dp,0,sizeof(dp));
23          dfs(0,0,0);
24          for(int i=1;i<n;i++)
25          {
26              memset(dp[i%2],0,sizeof(dp[1]));
27              for(int j=0;j<=rt;j++) if(dp[(i-1)%2][j])
28              {
29                  add=dp[(i-1)%2][j];
30                  dfs(i%2,~j&rt,0);
31              }
32          }
33          printf("%I64d\n",dp[(n-1)%2][rt]);
34      }
35      return 0;
36  }