首页 > 代码库 > UVA10918 - Tri Tiling(递推)

UVA10918 - Tri Tiling(递推)

UVA10918 - Tri Tiling(递推)

题目链接

题目大意:用2?1的瓷砖去铺3?n的框,问有多少种方式。

解题思路:首先n是奇数是无解的。这题应该说是递推,应该先明白这个状态可以由前面的哪些状态推来,画图可以发现n的状态可以由n - 2这个状态?3得到,还可以由n - 4这个状态?2得到等等。所以,f(n) = 3f(n - 2) + 2 f(n - 4) + .. + 2 f(0);再写出f(n - 2)的递推式,相减可以得到化简公式:f(n) = 4f(n - 2) - f(n - 4),边界f(0) = 1,f(2) = 3.

代码:

#include <cstdio>
#include <cstring>

const int maxn = 35;
typedef long long ll;
ll num[maxn];

void init() {

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

    for (int i = 4; i <= maxn - 5; i += 2) 
        num[i] = 4 * num[i - 2] - num[i - 4];
}

int main () {

    init();

    int n;
    while (scanf ("%d", &n) && n != -1) {

        printf ("%lld\n", num[n]);
    }
    return 0;
}

UVA10918 - Tri Tiling(递推)