poj_2506_Tiling_201407211555
2024-09-05 20:27:43
Tiling
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 7509 | Accepted: 3672 |
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.
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
2
8
12
100
200
Sample Output
3
171
2731
845100400152152934331135470251
1071292029505993517027974728227441735014801995855195223534251
Source
#include <stdio.h>
#include <string.h>
#define MAX 1000
int s[][MAX];
int main()
{
int i,j,k,t,n,len=;
memset(s,,sizeof(s));
s[][]=;
s[][]=;
s[][]=;
for(i=;i<=;i++)
{
t = ;
for(j=;j<=len;j++)
{
s[i][j]=s[i-][j]+*s[i-][j]+t;
if(s[i][j]>)
{
t=s[i][j]/;
s[i][j]%=;
}
else
t = ;
if(j==len&&t==)
len++;
}
}
while(scanf("%d",&n)!=EOF)
{
for(i=MAX-;i>&&(s[n][i]==);i--);
for(;i>=;i--)
printf("%d",s[n][i]);
printf("\n");
}
return ;
}
首先,无论任何一种方案,最左边的要么是一根竖的,要么是两根横的,要么是一个方的,对吧?所以:
当是一根竖时剩下的方案数是f[i-1]
当是两根横时剩下的方案数是f[i-2]
当是一个方时剩下的方案数是f[i-2]
故f[i]=f[i-1]+2*f[i-2] //递推+大数 注意:0的时候输出1(暂时没搞明白为什么,请大神指教)。
最新文章
- ITIS-资料集合贴
- [Python] 网络爬虫和正则表达式学习总结
- <;<;redis设计和实现>;>;读书笔记
- mapreduce出现类似死锁情况
- 记录今天学习python中for与while循环针对break和continue的用法
- Sharepoint 2013 列表使用JS Link
- LA 3415 (二分图+最大独立集)
- iOS 使用Xcode和Instruments调试解决iOS内存泄露(链接转)
- 【Sort Colors】cpp
- [转]C#中的?和??
- windows server 2012R2 网络慢的那些事
- SDUT 1269 走迷宫(BFS)
- Droppable(放置)组件
- sizeof与类,继承,virtual的种种
- 点击table中的某一个td,获得这个tr的所有数据
- 知物由学|游戏开发者如何从容应对Unity手游风险?
- MySql 从SQL文件导入
- js操作DOM对象
- 39.纯 CSS 创作一个表达怀念童年心情的条纹彩虹心特效
- 为什么要使用断路器Hystrix?