poj 2411 Mondriaan's Dream 【dp】

题目：

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;
}