首页 > 代码库 > POJ2506 (Tiling)

POJ2506 (Tiling)

2024-08-01 09:40:24   222人阅读

                                     Tiling
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 7755 Accepted: 3770

Description

In how many ways can you tile a 2xn rectangle by 2x1 or 2x2 tiles? Here is a sample tiling of a 2x17 rectangle.

Input

Input is a sequence of lines, each line containing an integer number 0 <= n <= 250.

Output

For each line of input, output one integer number in a separate line giving the number of possible tilings of a 2xn rectangle.

Sample Input

2812100200

Sample Output

317127318451004001521529343311354702511071292029505993517027974728227441735014801995855195223534251

Source

The UofA Local 2000.10.14
 
刚拿到这个题的时候,觉得并不是非常难,就是简单的递推,公式很快的就找出来了. p = a[i - 2][j] * 2 + a[i - 1][j] + k.
难点有两个,大数处理 和 n=0时,输出的是1 !!!!! (至今不知道为什么!!!)
代码:
#include <stdio.h>#include <string.h>int a[310][310];int main(){    int n, i, j, s, k, p;    while (scanf("%d", &n) != EOF)    {        memset(a, 0, sizeof(a));        a[0][0] = 1;//初始化        a[1][0] = 1;        a[2][0] = 3;        if (n <= 2)        {            printf("%d\n", a[n][0]);        }        else        {            s = 1;            for (i = 3; i <= n; ++i)            {                k = 0; //记录是否超过十                p = 0;                for (j = 0; j < s; ++j)                {                    p = a[i - 2][j] * 2 + a[i - 1][j] + k;                    a[i][j] = p % 10;                    k = p / 10;                }                if (k)//位数增加一位时的处理                {                    a[i][s] = k;                    s ++;                }            }            for (i = s - 1; i >= 0; --i)            {                printf("%d", a[n][i]);            }            printf("\n");        }    }    return 0;}

 

POJ2506 (Tiling)


联系
我们