多米诺骨牌放置问题(状压DP)

时间：2025-03-12 13:04:13

例题：

最近小A遇到了一个很有趣的问题:
现在有一个\(n\times m\)规格的桌面，我们希望用\(1 \times 2\)规格的多米诺骨牌将其覆盖。
例如,对于一个\(10 \times 11\)的桌面，下面为一种合法覆盖方案：
多米诺骨牌放置问题(状压DP)

那么给定n、m，应该如何覆盖呢？
但是小A并不满足于覆盖桌面，他希望知道能够覆盖整个桌面的合法方案数。
输入有 \(t\) 组数据，对于每组数据：
输入\(n、m\)，输出合法方案数\(ans\),答案\(ans\)对\(10^9+7\)取模，每个答案占一行。
以输入两个\(0\)为终止标志，输入保证\(n \times m\)为偶数 , \(t \leq 5\)。
***

子任务：

数据范围1 : \(n、m\leq 4\)

咳咳咳.... 滑稽吧。
直接暴力DFS一下即可。
复杂度：\(O(?)\)
***

数据范围2 : \(n、m \leq 10\)

思路解析：

以每一行来状压DP，假设\(m \leq n\)：
用一个二进制数表示每一行的状态，一共有: \(2^m\) 种，1代表放了，0代表没放。
那么每次枚举上一次的状态\(k\)，枚举这一次的状态\(j\)，然后检查一下是否可以转移。
如果可以，直接\(f[i][j] = f[i][j] + f[i-1][k];\)
可以转移的条件 自己yy ，考虑三种情况：不放，横放，竖放。
一个小技巧：竖放的情况只在后面那一格填1，保证合法。
时间复杂度\(O(t \times n \times {(2^m)}^2)\)

实现代码：

#include<bits/stdc++.h>
using namespace std;

long long f[13][2048]; int n,m,mx;

bool check(int s,int t){
    int r = 0,g = 0;
    for(int i = 0; i < m; i ++)
        r |= ((s&(1<<i)) ? 0:(1<<i));
    if((r&t) != r)return false;
    r = 0;
    for(int i = 0; i <= m; i ++){
        if(((1<<i)&s) && ((1<<i)&t))g = (g+1)%2;
        else if(g)return false;
    }
    return true;
}

int main(){
    while(scanf("%d %d\n",&n,&m)){
        if(!n && !m)break;
        if(n < m)swap(n , m);
        memset(f,0,sizeof(f));
        mx = (1<<m) - 1;
        f[0][mx] = 1;
        for(int i = 1; i <= n; i ++)
            for(int j = 0; j <= mx; j ++)
                for(int k = 0; k <= mx; k ++)
                    if(check(k,j))f[i][j] += f[i-1][k];
        cout<<f[n][mx]<<endl;
    }return 0;
}

数据范围3： \(n、m \leq 15\)

思路解析：

显然上一种状压\(DP\)会超时
以每一格来状压DP，假设\(m \leq n\)，
把棋盘从上往下，从左往右分为\(n \times m\)个阶段，每一个格子对应一个。
那么把轮廓线压入状态中，一共有\(2^m\)种状态。
如图：
多米诺骨牌放置问题(状压DP)

图中黄色格子为当前决策格，他有两种决策，放或者不放。
那么当前枚举的历史状态\(k\)为{ \(k_4k_3k_2k_1k_0\) }
那么对应的三种放置方法：
不放：新状态为{ \(k_3k_2k_1k_00\) } , 条件为\(k4=1\)
上放：新状态为{ \(k_3k_2k_1k_01\) } , 条件为\(k4=0\)并且当前不是第一行。
右放：新状态为{ \(k_3k_2k_111\) } , 条件为\(k4-1\)并且当前不是第一列。
还不懂得怎么设状态的可以去看刘汝佳(ORZ)的训练指南(蓝书)的P384-386。
时间复杂度：\(O(t \times n \times m \times 2^m)\)

实现代码：

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

long long f[2][2048]; int cur,n,m,mx;

int main(){
    freopen("testdate.in","r",stdin);
    while(scanf("%d %d\n",&n,&m)){
        if(!n && !m)break;
        if(n < m)swap(n , m);
        mx = (1<<m) - 1; cur = 0;
        memset(f,0,sizeof(f));
        f[cur][mx] = 1;
        for(int i = 1; i <= n; i ++)
            for(int j = 0; j < m; j ++){
                cur^=1;
                memset(f[cur],0,sizeof(f[cur]));
                //自上往下三种转移分别为：不放、上方、右放。
                for(int k = 0; k <= mx; k ++){
                    if(k & (1<<(m-1))){
                        f[cur][(k<<1)^(1<<m)] += f[cur^1][k];
                        if(j && !(k&1))f[cur][((k<<1)|3)^(1<<m)] += f[cur^1][k];
                    }
                    else if(i)f[cur][(k<<1)|1] += f[cur^1][k];
                }

            }
        printf("%lld\n",f[cur][mx]);
    }return 0;
}

相关文章