题目大意：
给你一个n*m的格子，让你用1*2的长方形不重叠地铺满，问总共有几种铺法。
思路：
轮廓线DP。
枚举当前右下角(i,j)，那么有不放、往上放和往左放三种情况。
对于三种情况分别讨论和转移。
状压的状态不是当前行的状态，而是当前轮廓线的状态。
1 #include<cstdio> 2 #include<cctype> 3 #include<cstring> 4 typedef long long int64; 5 inline int getint() { 6 register char ch; 7 while(!isdigit(ch=getchar())); 8 register int x=ch^'0'; 9 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 10 return x; 11 } 12 const int M=12; 13 int64 f[2][1<<M]; 14 bool cur; 15 int n,m; 16 inline void update(const int &a,const int &b) { 17 if(b&(1<<m)) f[cur][b^(1<<m)]+=f[cur^1][a]; 18 } 19 int main() { 20 for(;;) { 21 n=getint(),m=getint(); 22 if(!n&&!m) return 0; 23 memset(f[0],0,sizeof f[0]); 24 cur=0; 25 f[0][(1<<m)-1]=1; 26 for(register int i=0;i<n;i++) { 27 for(register int j=0;j<m;j++) { 28 cur^=1; 29 memset(f[cur],0,sizeof f[cur]); 30 for(register int k=0;k<(1<<m);k++) { 31 update(k,k<<1); 32 if(i&&!(k&(1<<(m-1)))) update(k,(k<<1)^(1<<m)^1); 33 if(j&&!(k&1)) update(k,(k<<1)^3); 34 } 35 } 36 } 37 printf("%lld ",f[cur][(1<<m)-1]); 38 } 39 }