SPOJ:M3TILE解决方案说明

Question

我一直在努力解决这个编程问题,但由于我无法理解,我在网上找到了一个解决方案.但我真的不明白为什么这个解决方案有效..

任务是计算3*n(n >= 0,n是唯一输入)矩形可用多少种方式完全填充2*1多米诺骨牌.

例如(红线代表多米诺骨牌):

这是我在阅读文本时首先在一张纸上绘制的内容,我看到3*2矩形可以有三种可能的组合,如果n是奇数,则解是0,因为没有办法然后填满整个矩形(一块将始终被多米诺骨牌覆盖).

所以我认为解决方案很简单3^n,如果n是偶数,并且0,如果n是奇数.原来,我错了.

我发现了一个相对简单的解决方案:

#include <iostream>

using namespace std;

int main()
{
    int arr[31];

    arr[0]=1;
    arr[1]=0;
    arr[2]=3;
    arr[3]=0;

    for(int i = 4; i < 31; i++) {
        arr[i] = arr[i-2] * 4 - arr[i-4]; //this is the only line i don't get
    }

    int n;

    while(1) {
        cin >> n;

        if(n == -1) {
            break;
        }

        cout << arr[n] << endl;
    }

    return 0;
}

为什么这样做？!

Answer 1

让我们用瓷砖T(n)平铺3×n电路板的方式数量2×1.另外,让我们P(n)可以通过瓷砖3×n移除一个角来平铺电路板的方式2×1.假设n足够大(>= 4).

然后考虑如何从左边开始平铺(或者右边,无关紧要).

您可以通过两种方式将瓷砖放在左上角,垂直或水平.如果将其垂直放置,则必须将覆盖左下角的瓷砖水平放置,从而进行配置

|
==

这留下P(n-1)了平铺剩余部分的方法.如果将其水平放置,可以将瓷砖水平或垂直放置在左下角.如果你垂直放置它,你处于和以前一样的情况,只是反射,如果你把它水平放置,你必须在它们之间水平放置一块瓷砖,

==
==
==

留给你一块3×(n-2)板.从而

T(n) = T(n-2) + 2*P(n-1)              (1)

现在,考虑到3×(n-1)一个已移除(已经覆盖)角落的板(让我们假设左上角),您可以在其下方垂直放置一块瓷砖,

=
|

然后让你用一块3×(n-2)板来铺砖,或者你可以在它下面水平放置两块瓷砖

=
==
==

然后你别无选择,只能将另一块瓷砖水平放置在顶部,离开你

===
==
==

用3×(n-3)板子减去角落,

P(n-1) = T(n-2) + P(n-3)

加起来,

T(n) = T(n-2) + 2*(T(n-2) + P(n-3))
     = 3*T(n-2) + 2*P(n-3)                            (2)

但是,使用(1)与n-2到位的n,我们看到,

T(n-2) = T(n-4) + 2*P(n-3)

要么

2*P(n-3) = T(n-2) - T(n-4)

插入它会(2)产生重复

T(n) = 4*T(n-2) - T(n-4)

QED