题目大意：一个矩阵，只能放1*2的木块，问将这个矩阵完全覆盖的不同放法有多少种。
解析：如果是横着的就定义11，如果竖着的定义为竖着的01，这样按行dp只需要考虑两件事儿，当前行&上一行，是不是全为1，不是说明竖着有空（不可能出现竖着的00），另一个要检查当前行里有没有横放的，但为奇数的1。
原代码链接：http://blog.csdn.net/accry/article/details/6607703
首先我个人感觉，横着是11，竖着是01 这个方法很牛逼，然后就是先预处理ok数组，之后就要判断符合的情况，最后写dp方程，先写边界，再写之后。
之后枚举s，s1两种状态，判断s行，s1行 两行在一起是否可行，还有一个有意思的地方就是，中间的行数只要按位与==full-1就可以，但最后一行必须是全为full-1才行！！
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
#define fi first
#define se second
#define prN printf("\n")
#define SI(N) scanf("%d",&(N))
#define SII(N,M) scanf("%d%d",&(N),&(M))
#define SIII(N,M,K) scanf("%d%d%d",&(N),&(M),&(K))
#define cle(a,val) memset(a,(val),sizeof(a))
#define rep(i,b) for(int i=0;i<(b);i++)
#define Rep(i,a,b) for(int i=(a);i<=(b);i++) int N,M;
ll dp[1<<11][11];//注意这，状态数是第一维
bool ok[1<<11];
int full; //用来初始化ok数组，这个数组存着可行的状态（就是横着，并且有连着的两个1的时候，这就相当于放了一个横着的1*2木块，
//剩下的0可以放竖着的，但x状态与y状态 按位“|”的时候，如果==full-1 那就可行 ）
bool judge(int n)
{
int bit=0;
while(n)
{
if ((n&1))
bit++;
else
{
if ((bit&1))
return false;
}
n>>=1;
}
if ((bit&1))
return false;
return true;
}
bool judge2(int x,int y)
{
if ((x|y)!=full-1)//x与y 这两个状态必须要能完全覆盖两行才能继续进行
return false;
//还有可能是奇数的1的情况，所以要返回ok数组的值
return ok[(x&y)];
} int main()
{
#ifndef ONLINE_JUDGE
freopen("C:\\Users\\Zmy\\Desktop\\in.txt","r",stdin);
// freopen("C:\\Users\\Zmy\\Desktop\\out.txt","w",stdout);
#endif // ONLINE_JUDGE
full=1<<11;
rep(S,full)
if (judge(S))
ok[S]=1;
while(cin>>N>>M,N||M)
{
cle(dp,0);
full=1<<M; //初始化dp边界
rep(S,full)
if(ok[S])
dp[S][0]=1;
//求dp 1到 n-1
Rep(i,1,N-1)
{
rep(s,full)
{
rep(s1,full)
{
if (!judge2(s,s1)) continue;
dp[s][i]+=dp[s1][i-1];//只有在都是1的情况下才做+=操作
}
}
}
//输出全是1的情况，并且在n-1行
int s=(1<<M)-1;
printf("%I64d\n",dp[s][N-1]);
} return 0;
}