POJ 2411 Mondriaan's Dream【状压DP】

怼烎@ 2024-04-19 16:32 43阅读 0赞

题意：给你一个n\*m的矩阵，让你用1\*2的矩形覆盖全部，问你方案数。

思路：我们可以发现，每个小矩形有两种放置方式，横着放和竖着放，我们设dp\[i\]\[s\]表示第i行状态为s时的方案数。

当当前位为1表示当前位置是竖着放置的矩形的上半部分，0则表示其他情况。那么对于当前行某个状态s，我们从上一行的某个合法状态p转移过来，那么什么状态算是合法的呢？

1. s & p == 0   这样保证对于上一行的每个1，下一行都是0与之对应才能够放置

2. s|p 中所有连续0的个数都是偶数。 这样保证横着放的合法

我们可以预处理一下哪个状态满足2条件，然后都满足的就直接转移就好了。

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    #define ls rt << 1
    #define rs rt << 1|1
    #define mid ((l + r) >> 1)
    #define lson l, mid, ls
    #define rson mid + 1, r, rs
    const int maxn = 13;
    const int mod = 1e9 + 7;
    ll dp[maxn][1 << maxn]; //前i行状态为s时的方案数，1表示是竖着的上半部分，0表示其他情况
    bool vis[1 << maxn]; //判断连续0是否出现偶数次
    
    int main()
    {
        int n, m;
        while(~scanf("%d%d", &n, &m) && n + m)
        {
            memset(vis, 0, sizeof(vis));
            for(int i = 0; i < (1 << m); ++i) //预处理判断连续0是否偶数个
            {
                int cnt = 0, flag = 0;
                for(int j = 0; j < m; ++j)
                {
                    if((i >> j) & 1)
                    {
                        if(cnt & 1)
                        {
                            flag = 1;
                            break;
                        }
                        else cnt = 0;
                    }
                    else ++cnt;
                }
                if(flag) vis[i] = 0;
                else if(!(cnt & 1))
                    vis[i] = 1;
            }
            memset(dp, 0, sizeof(dp));
            dp[0][0] = 1;
            for(int i = 1; i <= n; ++i)
            {
                for(int s = 0; s < (1 << m); ++s)
                {
                    for(int p = 0; p < (1 << m); ++p)
                    {
                        if((s & p) == 0 && vis[s | p])
                            dp[i][s] += dp[i - 1][p];
                    }
                }
            }
            printf("%lld\n", dp[n][0]);
        }
        return 0;
    }