题意：给定一个n*m的方格，问你用3*1的格子覆盖掉这个方格有多少种方法。。
解题思路：主要是状态压缩+dp，状态压缩和dp很神，http://www.cppblog.com/Ayue/archive/2011/12/04/161446.aspx
解题代码：
1 // Author: darkdream 2 // Created Time: 2013年09月06日 星期五 20时03分39秒 3 4 #include<stdio.h> 5 #include<string.h> 6 #include<stdlib.h> 7 #include<time.h> 8 #include<math.h> 9 #define LL long long 10 //freopen("/home/plac/problem/input.txt","r",stdin); 11 //freopen("/home/plac/problem/output.txt","w",stdout); 12 LL pp[10] , num[10],zt,row,n,m,dp[34][100000]; 13 14 void dfs(LL pos, LL status) 15 { 16 if(pos == n) 17 { 18 dp[row+1][status] += dp[row][zt]; 19 return; 20 } 21 if(num[pos] == 0 ) 22 { 23 if(pos + 2 < n && num[pos+2] == 0 && num[pos+1] == 0 ) dfs(pos+3,status); 24 dfs(pos+1,status+ 2*pp[pos]); 25 } 26 else if(num[pos] == 1) 27 dfs(pos+1,status); 28 else { 29 dfs(pos+1,status+pp[pos]); 30 } 31 } 32 void change() 33 { 34 LL now = zt ,k = -1; 35 memset(num,0,sizeof(num)); 36 while(now) 37 { 38 num[++k] = now%3; 39 now = now/3; 40 } 41 42 } 43 int main(){ 44 pp[0] = 1; 45 for(int i = 1;i<= 9;i ++) pp[i] = pp[i-1]*3; 46 47 while(scanf("%lld %lld",&n,&m) && (m||n)) 48 { 49 if((m*n)%3 != 0 ) 50 { 51 printf("0 "); 52 continue; 53 } 54 memset(dp,0,sizeof(dp)); 55 dp[0][0] = 1; 56 LL nmax = pp[n]; 57 for(row = 0 ; row < m ; row ++) 58 for(zt = 0 ; zt < nmax; zt ++) 59 if(dp[row][zt]) 60 { 61 change(); 62 dfs(0,0); 63 } 64 printf("%lld ",dp[m][0]); 65 } 66 return 0 ; 67 }