1059: 贴瓷砖

题目描述

有一块大小是 2 * n 的墙面，现在需要用2种规格的瓷砖铺满，瓷砖规格分别是 2 * 1 和 2 * 2，请计算一共有多少种铺设的方法。

输入

输入的第一行包含一个正整数T（T<=20），表示一共有T组数据，接着是T行数据，每行包含一个正整数N（N<=30），表示墙面的大小是2行N列。

输出

输出一共有多少种铺设的方法，每组数据的输出占一行。

解析

最容易想到的解法就是DFS，模拟一遍整个铺瓷砖的过程，但是不出所料，时间超限~

既然不能用暴力解法，那就要去思考结果是不是可以通过一个递推式算出来的。要想写出递推式，就要去分解大问题，直到它的规模足够小，能直接得出结果。最小规模显然是n=1的情况，对于一个2*1的墙面，贴法只有1种。这时我们再去思考n=2的情况，由于n=2时就可以使用2*2的瓷砖，且可以将2*1的瓷砖横过来贴了，所以n=2的情况有点特殊，结果是3种。那么再想想n=3的情况，如果我们要拆解2*3的墙面，有两种方法：1.先用一块2*1的砖竖着贴在墙面最右边，这样剩下的就是2*2的墙面了，而n=2时的结果是3，这是我们已经知道的；2.用一块2*2的瓷砖贴在最右边，这样剩下的就是2*1的墙面，结果为1，但是注意，这种贴法还有另一种情况，那就是我们可以用两块2*1的瓷砖叠成一个2*2的瓷砖，所以这里其实有两种情况，所以结果应该为1*2=2。所以，对于2*3的墙面，结果就为3+1*2=5。

从n=3的例子我们可以看出来，当n>=3时，就可以尝试去分解问题了，对于一个2*n(n>=3)的墙面，其瓷砖贴法数为2*(n-1)的墙面贴法数和2*(n-2)的墙面贴法数的两倍的和。如果令f(n)表示为一面2*n的墙面的解，那么就有递推式：f(n)=f(n-1)+2*f(n-1)，特殊的，f(0)=0，f(1)=1，f(2)=3。

代码

AC代码：

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

int tiling(int i)
{
    if (i == 0) return 0;
    if (i == 1) return 1;
    if (i == 2) return 3;
    return tiling(i - 1) + tiling(i - 2) * 2;
}

int main()
{
    int n; cin >> n;
    while (n--) {
        int i; cin >> i;
        cout << tiling(i) << endl;
    }
    return 0;
}

顺便再贴一个自己的dfs解法的代码：

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

int m, ans = 0;
int** wall = new int*[3];

void tiling(int t, int n)
{
    if (t > m) {
        ans++;
        return;
    }
    if (wall[1][t] == 0) {
        if (wall[2][t] == 0) {
            wall[1][t] = wall[2][t] = n;
            tiling(t + 1, n + 1);
            wall[1][t] = wall[2][t] = 0;
            if (t + 1 <= m) {
                wall[1][t] = wall[2][t] = n;
                wall[1][t + 1] = wall[2][t + 1] = n;
                tiling(t + 2, n + 1);
                wall[1][t] = wall[2][t] = 0;
                wall[1][t + 1] = wall[2][t + 1] = 0;
            }
        }
        if (wall[1][t + 1] == 0) {
            wall[1][t] = wall[1][t + 1] = n;
            tiling(t, n + 1);
            wall[1][t] = wall[1][t + 1] = 0;
        }
    }
    else if (wall[2][t] == 0) {
        if (t + 1 <= m) {
            wall[2][t] = wall[2][t + 1] = n;
            tiling(t + 2, n + 1);
            wall[2][t] = wall[2][t + 1] = 0;
        }
    }
}

int main()
{
    int n; cin >> n;
    while (n--) {
        cin >> m;
        if (m <= 0) {
            cout << 0 << endl;
            continue;
        }
        for (int i = 1; i < 3; i++) {
            wall[i] = new int[m + 1];
            for (int j = 1; j < m + 1; j++)
                wall[i][j] = 0;
        }
        tiling(1, 1);
        cout << ans << endl;
        ans = 0;
    }
    return 0;
}