题意：
用一个2*1的骨牌来覆盖一个n*m的矩形，问有多少种方案？(1<=n,m<=11)
思路：
很经典的题目，如果n和m都是奇数，那么答案为0。同uva11270这道题。
只需要m个bit来记录状态行了，标记是否已经被覆盖到了。考虑当前格子，如果上面格子未覆盖，则必须放竖的，否则，将再也覆盖不到此格子；如果上面格子已经覆盖，而左边未覆盖，那么还可以选择放横的，或者是不放（左边若未覆盖可以由左下格子去考虑）。
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <deque>
#include <map>
#include <algorithm>
#include <vector>
#include <iostream>
#define pii pair<int,int>
#define INF 0x3f3f3f3f
#define LL long long
#define ULL unsigned long long
using namespace std;
const double PI = acos(-1.0);
const int N=;
LL dp[][<<], cur; LL cal(int n,int m)
{
if(n==m&&n%==) return ;
if(n<m) swap(n,m);
memset(dp[],,sizeof(dp[]));
dp[cur=][(<<m)-]=;
for(int i=; i<=n; i++)
{
for(int j=; j<=m; j++)
{
cur^=;
memset(dp[cur],,sizeof(dp[cur]));
int r=(<<m)-;
for(int s=; s<(<<m); s++)
{
LL v=dp[cur^][s];
if( (s&(<<m-))== ) //必须放竖
dp[cur][(s<<)+]+=v;
else
{
dp[cur][(s<<)&r]+=v; //不放
if( j> && (s&)== ) //放横
dp[cur][((s<<)+)&r]+=v;
}
}
}
}
return dp[cur][(<<m)-];
} int main()
{
freopen("input.txt","r",stdin);
int n, m;
while(scanf("%d%d",&n,&m),n+m)
printf("%lld\n",cal(n,m));
return ;
}
AC代码