• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

Tri Tiling·递推

互联网 diligentman 1周前 (02-17) 9次浏览

Tri Tiling

  • 题目信息
    • 输入
    • 输出
    • 测试样例
    • 来源
  • 解答
  • 想法

题目信息

In how many ways can you tile a 3xn rectangle with 2×1 dominoes?
Here is a sample tiling of a 3×12 rectangle.
有多少种方法可以用2×1多米诺骨牌平铺3xn矩形?
下面是3×12矩形的平铺示例。
Tri Tiling·递推

输入

Input consists of several test cases followed by a line containing -1. Each test case is a line containing an integer 0 <= n <= 30.
输入由几个测试用例组成,最后一行是一个-1。每个测试用例都是一行,包含一个整数’0<=n<=30’。

输出

For each test case, output one integer number giving the number of possible tilings.
对于每个测试用例,输出一个整数,给出可能的平铺数。

测试样例

2
8
12
-1
3
153
2131

来源

Waterloo local 2005.09.24

解答

#include<iostream>

#define ll long long
using namespace std;

ll num[40];

int main()
{
    //freopen("E://test.txt", "r", stdin);
    ios::sync_with_stdio(false);
    int n;
    num[0] = 1;
    num[1] = 0;
    num[2] = 3;
    for (int i = 3; i <= 35; i++)
    {
        if (i % 2 != 0)
        {
            num[i] = 0;
        }
        else
        {
            num[i] = num[i - 2] * 4 - num[i - 4];
        }
    }
    while (cin >> n)
    {
        if (n == -1)
        {
            break;
        }

        cout << num[n] << endl;
    }
    return 0;
}

想法


程序员灯塔
转载请注明原文链接:Tri Tiling·递推
喜欢 (0)