题意:求把(N*M(N,M<=11))的棋盘分割成若干个(1*2)的长方形,有多少种方案.
分析:"数据这么小,状压DP".考虑把每一行的状态用一个(M)位的二进制数表示,对于每一行的某一列,如果它把一个竖着的(1*2)的长方形拆成了两半,那么这一位用1表示它是一个长方形的上一半（这里一定要明确是表示上面一半）,其余情况用0表示.
设(f[i][j])表示第(i)行,状态为(j)时,前(i)行分割方案的总数.(j)是用十进制整数记录的一个(M)位二进制数.
第(i-1)的状态(k)要能够转移到第(i)行的状态(j),当且仅当:
1、(j)&(k==0),即数字1的下面不能是1，只能是0（这里不理解的话，在好好理解一下前面关于“1”的定义）
2、(j)^(k)的结果用二进制表示，每一段连续的0都必须是偶数个（这些0代表若干个横着的长方形，如果是奇数个0显然拼不出来）
对于上述情况2，我们可以预处理出来，记录在集合S中,则，
(f[i][j]=sum f[i-1][k])(j&k=0 且 j|k∈S)
初始化(f[0][0]=1),其余均为0,求出(f[n][0]).
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;
inline int read(){
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
return s*w;
}
const int N=2050;
int bj[N];LL f[15][N];
int main(){
while(1){
int n=read(),m=read();if(!n&&!m)break;
f[0][0]=1;
//预处理集合S：
for(int i=0;i<(1<<m);i++){
int cnt=0,res=0;
for(int j=0;j<m;j++){
if((i>>j)&1)res|=cnt,cnt=0;
else cnt^=1;
}
bj[i]=cnt|res?0:1;
}
//直接枚举：
for(int i=1;i<=n;i++){
for(int j=0;j<(1<<m);j++){
f[i][j]=0;
for(int k=0;k<(1<<m);k++)
if((j&k)==0&&bj[j|k])
f[i][j]+=f[i-1][k];
}
}
printf("%lld
",f[n][0]);
}
return 0;
}