【题目分析】
用1*2的牌铺满n*m的格子。
刚开始用到动规想写一个n*m*2^m，写了半天才知道会有重复的情况。
So Sad。
然后想到数据范围这么小，爆搜好了。于是把每一种状态对应的转移都搜了出来。
加了点优（gou）化（pi），然后poj上1244ms垫底。
大概的方法就是考虑每一层横着放的情况，剩下的必须竖起来的情况到下一层取反即可。
然后看了 《插头DP-从入门到跳楼》 这篇博客，怒抄插头DP
然后16ms了，自己慢慢YY了一下，写出了风（gou）流（pi）倜（bu）傥（tong）的代码
UPD：发现完全不需要轮廓线，直接把轮廓线断开一小段就可以转移了，更加坚定自己的算法渣了
【代码】
状压DP
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define F(i,j,k) for (int i=j;i<=k;++i)
#define D(i,j,k) for (int i=j;i>=k;--i)
#define ll long long
ll dp[12][1<<12];
int pos[12],n,m,to[1<<12];
void print(int x){F(i,0,m-1)printf("%d",(x>>i)&1);}
void dfs(int x)
{
if (to[x]) return ;
to[x]=1;
F(i,0,m-2)
if ((!(x&pos[i]))&&(!(x&pos[i+1])))
dfs(x|pos[i]+pos[i+1]);
}
int main()
{
while (scanf("%d%d",&n,&m)!=EOF&&n&&m)
{
memset(dp,0,sizeof dp); int all=(1<<m)-1;
F(i,0,m) pos[i]=1<<i; dp[0][(1<<m)-1]=1;
F(i,0,n-1)
{
F(j,0,(1<<m)-1)
{
memset(to,0,sizeof to);
int aim=j^all; dfs(aim);
F(k,0,(1<<m)-1)
if (to[k]) dp[i+1][k]+=dp[i][j];
}
}
printf("%lld\n",dp[n][(1<<m)-1]);
}
}
插头DP
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; long long dp[2][1<<11]; int main()
{
int n,m;
while(scanf("%d%d",&n,&m),(n||m))
{
int total=1<<m;
int pre=0,now=1;
memset(dp[now],0,sizeof(dp[now]));
dp[now][0]=1; for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
swap(now,pre);
memset(dp[now],0,sizeof(dp[now])); for(int S=0;S<total;S++) if( dp[pre][S] )
{
dp[now][S^(1<<j)]+=dp[pre][S];
if( j && S&(1<<(j-1)) && !(S&(1<<j)) )
dp[now][S^(1<<(j-1))]+=dp[pre][S];
}
} printf("%lld\n",dp[now][0]);
}
}
自己写的代（gou）码（pi）
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
#define F(i,j,k) for (int i=j;i<=k;++i)
ll dp[2][1<<12];
int n,m;
void print(int x)
{F(i,0,m)printf("%d",(x>>i)&1);}
int main()
{
while (scanf("%d%d",&n,&m)!=EOF&&n&&m)
{
if (n<m) swap(n,m);
int now=1,pre=0;
memset(dp[now],0,sizeof dp[now]);
dp[now][0]=1;
F(i,0,n-1)
F(j,0,m-1)
{
now^=1;pre^=1;
memset(dp[now],0,sizeof dp[now]);
F(s,0,(1<<(m+1))-1) if (dp[pre][s])
{
if ((s&(1<<j))&&!(s&(1<<(j+1)))) dp[now][s^(1<<j)]+=dp[pre][s];
if (!(s&(1<<j))&&!(s&(1<<(j+1)))) dp[now][s^(1<<j)]+=dp[pre][s],dp[now][s^(1<<(j+1))]+=dp[pre][s];
if (!(s&(1<<j))&&(s&(1<<(j+1)))) dp[now][s^(1<<(j+1))]+=dp[pre][s];
}
if (j==m-1)
{
now^=1;pre^=1;
memset(dp[now],0,sizeof dp[now]);
F(s,0,(1<<m)-1) if (dp[pre][s]&&!(s&(1<<m)))
dp[now][(s<<1)&((1<<(m+1))-1)]+=dp[pre][s];
}
}
printf("%lld\n",dp[now][0]);
}
}