POJ2506——Tiling
2024-10-19 00:27:28
Tiling
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 题目大意:给一个2*n的棋盘,用三种方块(2*2,1*2,2*1)将其铺满,为有多少种可能性。
解题思路:显然f(n)=f(n-1)+f(n-2)*2简单递推就可以。。 但是看样例就知道longlong也存不开。用string型来进行大数相加
Code:
#include<cstdio>
#include<string>
#include<iostream>
using namespace std;
string a[];
string Add(string s1,string s2)
{
if (s1.length()<s2.length())
swap(s1,s2);
int i,j;
for(i=s1.length()-,j=s2.length()-;i>=;i--,j--)
{
s1[i]=s1[i]+(j>=?s2[j]-'':);
if(s1[i]-''>=)
{
s1[i]=(s1[i]-'')%+'';
if(i) s1[i-]++;
else s1=''+s1;
}
}
return s1;
}
int main()
{
int i,n;
a[]="",a[]="",a[]="";
for (i=; i<=; i++)
a[i]=Add(Add(a[i-],a[i-]),a[i-]);
while (cin>>n)
cout<<a[n]<<endl;
return ;
}
最新文章
- UIBezierPath-完善曲线
- 我的权限系统设计实现MVC4 + WebAPI + EasyUI + Knockout(一)
- office中通过宏添加快捷键
- 关于插件管理器Alcatraz
- Leetcode Move Zeros
- Linux 读书笔记 一
- c# 获取excel所有工作表
- 转载 近期微博吐槽言论存档,涉及“性能优化”、C++陋习等
- 20 个用于处理页面滚动效果的 jQuery 插件
- .Net的基础概念
- MD5验证工具:md5sum
- [转载]opencv +linux
- Struts学习之模型驱动
- MYSQL:基础—存储过程
- 1.2 N层架构
- 一篇关于Python装饰器的博文
- Linux下的I/O模型以及各自的优缺点
- C和C#的区别
- [转]最常用的15大Eclipse开发快捷键技巧
- LeetCode第十二题-将数字转化为罗马数字
热门文章
- Poj 2996 Help Me with the Game
- Adobe Photoshop CS4 Extended CS4 激活序列号
- QT设置窗口屏幕居中
- TreeView递归取值
- SQL Server如何使用XML格式传输解析
- poj 3641 Pseudoprime numbers Miller_Rabin测素裸题
- C#网络编程(1)
- linux命令后面常见的>;/dev/null 和 2>;&;1 的含义
- EXTJS 4.2 资料 跨域的问题
- poj 3013 Big Christmas Tree (最短路径Dijsktra) -- 第一次用优先队列写Dijsktra