嘘~ 正在从服务器偷取页面 . . .

UVA11270 Tiling Dominoes 题解

算法 DP

发布日期: 2024-04-24

更新日期: 2024-04-24

文章字数: 752

UVA11270 Tiling Dominoes 题解

题目链接：Tiling Dominoes

题意：

给定一个 \(n\times m(\le 100)\) 的矩形网格，在里面放 \(1\times 2\) 的多米诺骨牌，求方案数

以下是一种方案。

注意，旋转后本质相同的方案也算作不同方案。

这道题是比较简单的插头dp，所以本文会以简单的方式来介绍插头dp。

插头dp作为模板题是黑题的高级算法，本身的思想其实没有那么复杂，它实际上就是状压dp。

观察本题的图片可以发现，我们没法从某个子矩形的答案直接转移到整个矩形

于是我们就考虑最朴素的，一格一格的逐行递推，也就是下图这种形式（~~图是题解区偷的~~）

然后我们发现转移需要上面格子和左边格子的填充信息，而只记录这两个信息就无法转移

又因为这个 \(n\) 比较小，考虑状压dp。

设 \(f(i,S)\) 表示处理到第 \(i\) 行，上图中白色格子的填充状态为 \(S\) 时的方案数。

然后分类讨论上面格子和左面格子的填充情况：

上面没有，左边没有。这种情况必须向上放。
上面没有，左边有。这种情况必须向上放。（转移可以和上一行合并）
上面有，左边没有。这种情况可以向左放，也可以不放。
上面有，左边有。这种情况必须不放。

那么这道题就做完了，是不是很简单。

事实上这种状压dp就是简单的插头dp，只不过插头dp的板子题需要讨论的情况复杂不少。

时间复杂度 \(\mathcal{O}(n^22^n)\) ，认为 \(n,m\) 同阶。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

int n,m,cur,bits,pw2[15],f[2][2333];
void solve()
{
    if((n * m) & 1) { cout << "0\n"; return; }
    memset(f, 0, sizeof(f)); if(n < m) swap(n, m);
    cur = 0, bits = (1 << m) - 1; f[cur][bits] = 1;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
        {
            cur ^= 1; memset(f[cur], 0, sizeof(f[cur]));
            for(int k = 0; k <= bits; k++)
            {
                if(!(k & (1 << j))) { f[cur][k | (1 << j)] += f[cur ^ 1][k]; }
                if(j && (k & (1 << j)) && !(k & (1 << (j - 1))))
                    f[cur][k | (1 << (j - 1))] += f[cur ^ 1][k];
                if(k & (1 << j)) f[cur][k ^ (1 << j)] += f[cur ^ 1][k]; // 2 types
            }
        }
    cout << f[cur][bits] << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    pw2[0] = 1;
    for(int i = 1; i < 14; i++) pw2[i] = pw2[i - 1] << 1;
    while(cin >> n >> m) solve();
    return 0;
}