这题是2015年暑假DP考试里考的。。上次不会做抄了代码，这次又不会做抄代码。。。以前状压DP的题简直白做了
这题关键是用一个数组记录上一行状态为s和这一行状态为t能否并存，用一个dfs预处理这个数组，然后转移就很简单了。
每种木板只有两种情况，横着放和竖着放，dfs里面对其进行枚举。
#include<cstdio> #include<cstring> #define maxl 12 int n,m,lim; bool b[1<<maxl][1<<maxl]; long long f[maxl][1<<maxl]; void dfs(int from,int step,int to) { if(step==m) { b[from][to]=1; return; } if((1<<step)&from) dfs(from,step+1,to); else { if(!((1<<(step+1))&from) && step<=m-2) dfs(from,step+2,to); dfs(from,step+1,to|(1<<step)); } } void prework() { lim=1<<m; memset(b,0,sizeof(b)); for(int i=0;i<lim;i++) dfs(i,0,0); } void mainwork() { memset(f,0,sizeof(f)); f[0][0]=1; for(int i=0;i<n;i++) for(int j=0;j<lim;j++) for(int k=0;k<lim;k++) if(b[j][k]) f[i+1][k]+=f[i][j]; } void print() { printf("%lld\n",f[n][0]); } int main() { while(~scanf("%d%d",&n,&m)) { if(n==0 && m==0) break; prework(); if((n*m)%2==1) { printf("0\n"); continue; } mainwork(); print(); } return 0; }