题目： id=2411" target="_blank">poj 2411 Mondriaan's Dream
题意：给出一个n*m的矩阵，让你用1*2的矩阵铺满，然后问你最多由多少种不同的方案。
分析：这是一个比較经典的题目。网上各种牛B写法一大堆。题解也是
我们能够定义状态：dp【i】【st】：在第 i 行状态为 st 的时候的最慷慨案数、
然后转移方程：dp【i】【st】 = sum （dp【i-1】【ss】）
即全部的当前行都是由上一行合法的状态转移而来。
而状态的合法性由两种铺法得到。第一种横放。注意要求前一行全满。然后竖放，上一行为空。能够留空。
AC代码：
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const long long N = 15;
long long dp[N][1<<N];
long long ans[N][N];
long long n,m;
bool solve(long long st)
{
long long tmp=0;
for(long long i=0; i<m; i++)
{
if(st&(1<<i))
tmp++;
else
{
if(tmp%2)
return false;
tmp=0;
}
}
if(tmp%2)
return false;
return true;
}
bool cmp(long long st,long long up)
{
for(long long i=0; i<m; i++)
{
if(st&(1<<i))
{
if(up&(1<<i))
{
if(i==m-1 || !(st&(1<<(i+1))) || !(up&(1<<(i+1))))
return false;
else
i++;
}//否则的话竖放
}
else
{
if(!(up&(1<<i)))
return false;
}
}
return true;
}
int main()
{
memset(ans,0,sizeof(ans));
while(~scanf("%lld%lld",&n,&m))
{
if(n==0 && m==0)
break;
if((m*n)%2)
{
printf("0\n");
continue;
}
if(m>n)
swap(m,n);
if(ans[n][m])
{
printf("%lld\n",ans[n][m]);
continue;
}
memset(dp,0,sizeof(dp));
long long len = 1<<m;
for(long long i=0; i<len; i++)
{
if(solve(i))
dp[1][i]=1;
}
for(long long i=2; i<=n; i++)
{
for(long long st=0; st<len; st++) //当前行
{
for(long long k = 0; k<len; k++) //上一行
{
if(cmp(st,k))
dp[i][st]+=dp[i-1][k];
}
}
}
printf("%lld\n",dp[n][len-1]);
ans[n][m] = dp[n][len-1];
}
return 0;
}