POJ 2506 Tiling (递推 + 大数加法模拟 )
2024-08-29 09:06:26
Tiling
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 7965 | Accepted: 3866 |
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
算法分析:递推公式:f[i]=f[i-1]+f[i-2]*2; 此公式也不是我自己推导出来的,我也没推导出来,我从ACM之家上的java代码看出的
公式。
代码:
#include <stdio.h>
#include <string.h>
int a[1001][501]={0};
int main()
{
int n;
int i, j, h, e;
a[0][500] = 1;
a[1][500] = 1;
a[2][500] = 3;
for(i=3; i<=250; i++)
{
h = 0;
for(j=500; j>=0; j--)
{
e=a[i-2][j]*2+a[i-1][j]+h;
a[i][j]=e%10;
h=e/10;
}
}
while(scanf("%d", &n)!=EOF)
{
if(n==0)
{
printf("1\n"); continue;
}
i = 0;
while(a[n][i]==0)
{
i++;
}
for(i; i<=500; i++)
{
printf("%d", a[n][i] );
}
printf("\n");
}
return 0;
}
这还有一份java代码,正确的!
import java.util.*;
import java.math.*;
public class Main{
static BigInteger[] ans; //
public static void main(String[] args){
Scanner reader=new Scanner(System.in);
ans = new BigInteger[251];
ans[0]=BigInteger.valueOf(1);
ans[1]=BigInteger.valueOf(1);
ans[2]=BigInteger.valueOf(3);
for(int i=3; i<=250; i++)
{
ans[i] = ans[i-1].add(ans[i-2].multiply(BigInteger.valueOf(2)));
}
int n;
while(reader.hasNextInt()){
n=reader.nextInt();
System.out.println(ans[n]);
}
}
}
最新文章
- (翻译)《Hands-on Node.js》—— Why?
- SUBLIME TEXT 2 设置文件详解
- POJ2823 Sliding Window
- WPF 控件截图位置不正确的问题
- Converting Storyboard from iPhone to iPad
- NSString、NSMutableString基本使用
- SQlserver表连接
- php环境配置优化
- redhat linux 5上创建本地yum源
- 使用AOP 使C#代码更清晰
- .bat文件设置IP、DNS
- CentOS 7 安装samba服务
- SQL Pretty Printer for SSMS 很不错的SQL格式化插件
- kafka告警简单方案
- Win10系统的SurfacePro4如何重装系统-2 重装WIN10系统
- win7 win10开启网络访问(网络访问 无法访问 网络访问需要输入密码 等问题处理)
- SPI OLED 驱动
- npm和yarn
- 关于redis与memcached区别(转载自stackoverflow)
- Python中的format()函数
热门文章
- Codeforces Round #321 (Div. 2) Kefa and Park 深搜
- 文艺平衡树(Splay)
- POI2004
- 想用idea的update classes and resources找不到了,热部署无法使用
- sql server trace
- list all of the Oracle 12c hidden undocumented parameters
- 很多shell命令后面的单横杠和双横杠,原来这个意思
- 怎么在SQL查询的结果里加行号?
- UVA 12338 - Anti-Rhyme Pairs(后缀数组+RMQ)
- mysql flush详解