poj 2411 Mondriaan's Dream 【dp】

客官°小女子只卖身不卖艺 2022-08-13 00:51 22阅读 0赞

题目：[poj 2411 Mondriaan's Dream][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;
    }

[poj 2411 Mondriaan_s Dream]: http://poj.org/problem?id=2411