blingbling 摆砖块的第二题~~ 好吧。。。虽然代码是一样样的,就当是再梳理一下思路吧。
然后刚开始的时候RE了,不懂为什么,乱开数组,,,后来发现是每次h没有初始化成3。。。所以以后一定要不辞辛苦地初始化。
看到这道题可以用递归做,,,先mark一下,感觉看不懂,,,
#include <stdio.h> #include <string.h> #define maxn 14000 #define ll __int64 ll path[300][2],tan,h,w; ll dp[40][10]; void dfs(int d,int now,int pre) { if(d>w) return; if(d==w) { path[tan][0]=pre; path[tan++][1]=now; return; } dfs(d+1,now<<1|1,pre<<1); dfs(d+1,now<<1,pre<<1|1); dfs(d+2,now<<2|3,pre<<2|3); } int main() { h=3; while(1) { scanf("%I64d",&w); h=3; if(w==-1) break; if(w*h%2) {printf("0\n");continue;} memset(dp,0,sizeof(dp)); if(w>h) {int t=h;h=w;w=t;} tan=0; dfs(0,0,0); int i,j,k; dp[0][(1<<w)-1]=1; for(i=0;i<h;i++) for(j=0;j<tan;j++) dp[i+1][path[j][1]]+=dp[i][path[j][0]]; printf("%I64d\n",dp[h][(1<<w)-1]); } return 0; }