ZOJ Problem Set - 2563 Long Dominoes 【状压dp】

朱雀 2022-08-13 00:53 19阅读 0赞

题目：[ZOJ Problem Set - 2563 Long Dominoes][]

题意：给出1\*3的小矩形，求覆盖m\*n的矩阵的最多的不同的方法数？

分析：有一道题目是1 \* 2的，比较火，链接：[这里][Link 1]

这个差不多，就是当前行的状态对上一行有影响，对上上一行也有影响。所以

定义状态：dp【i】【now】【up】表示在第 i 行状态为now ，上一行状态为 up 时的方案数。

然后转移方程：dp【i】【now】【up】 = sum （ dp【i-1】【up】【uup】 ） 前提是合法

合法性的判断是比较难考虑的一点，因为是1 \* 3的，只能横着放和竖着放。

如果横着放，那么上面up 和 uup 的 3 格也必须是满的才行

如果竖着放，那么up 和 uup的当前格必须是空的，注意判断后变化up

如果用简单的枚举dp的话，四层循环会超时，所以我们要用up 和 upp 来深搜构造当前行，这样才能过。

AC代码：

枚举超时代码：

#include <cstdio>
    #include <cstring>
    #include <string>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;
    #define INT long long int
    const long long N = 9 ;
    const int inf = 0x3f3f3f3f;
    INT dp[31][1<<N][1<<N];
    int m,n;
    bool isit(int st)
    {
        int tmp=0;
        for(int i=0;i<m;i++)
        {
            if(st&(1<<i))
                tmp++;
            else
            {
                if(tmp%3)
                    return false;
            }
        }
        if(tmp%3)
            return false;
        return true;
    }
    INT solve(int now,int up,int uup)
    {
        for(int i=0;i<m;i++)
        {
            if(!(uup&(1<<i))) //判断上上一行为0
            {
                if(up&(1<<i))
                    return -1 ;
                else
                {
                    if(!(now&(1<<i)))
                         return -1 ;
                    else
                        up |= (1<<i) ;
                }
            }
            else
            {
                if(up&(1<<i) && now&(1<<i)) // 1 1 1
                {
                    if(i==m-2 || i==m-1)
                        return -1 ;
                    else if(!(now&(1<<(i+1))) || !(now&(1<<(i+2))) || !(up&(1<<(i+1))) || !(up&(1<<(i+2))) || !(uup&(1<<(i+2))) || !(uup&(1<<(i+1))))
                        return -1 ;
                    i+=2;
                }
            }
        }
        return up ;
    }
    int main()
    {
        while(~scanf("%d%d",&m,&n)&& m+n)
        {
            for(int st=0;st<(1<<m);st++)
            {
                if(!isit(st))
                    continue;
                for(int up=0;up<(1<<m);up++)
                {
                    if(isit(up)){
                        dp[2][st][up]=1;
                    }
                }
            }
            for(int i=3;i<=n;i++)
            {
                for(int no = 0;no < (1<<m); no++)
                {
                    for(int kp=0;kp<(1<<m);kp++)  //上行
                        dp[i][no][kp]=0;
                    for(int up=0;up<(1<<m);up++)  //上行
                    {
                        int temp ;
                        for(int st=0;st<(1<<m);st++) //上上行
                            if((temp = solve(no,up,st)) != -1)
                                dp[i][no][temp]+=dp[i-1][up][st];
                        //printf("%d\n",dp[i][up][up]);
                    }
                }
            }
            printf("%lld\n",dp[n][(1<<m)-1][(1<<m)-1]);
        }
        return 0;
    }

[ZOJ Problem Set - 2563 Long Dominoes]: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1563
[Link 1]: http://blog.csdn.net/y990041769/article/details/39924331