首页 > 代码库 > POJ2506 (Tiling)
POJ2506 (Tiling)
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)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。