题目描述: http://poj.org/problem?id=2506
题目大意: 使用2 * 1 和 2 * 2 的矩形铺砌2 * n 的矩形, 共有多少种方法?
分析:
假设f ( n ) 为铺砌 2 * n 的矩形的方法种数, 参见下图:
易得 f ( n ) = f ( n - 1 ) + 2 * f ( n - 2 );
f ( 1 ) = 1; f ( 2 ) = 3;
又因为本体要求处理的n 很大, 需要大数处理, 故用Java 的BigInteger 类, 免去用c++ 实现大数加法, 代价是牺牲一部分的性能...
注意f ( 0 ) 的取值, 参见代码
import java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[] args) { int n; //2 * n 的 n BigInteger[] a = new BigInteger[251]; a[0] = BigInteger.ONE; //令人上火的是a[0] 为 1,?????? //刚开始写a[0] 为 0,WA a[1] = BigInteger.ONE; a[2] = new BigInteger("3"); for(int i = 3; i <= 250; i++) { a[i] = a[i - 1].add(a[i - 2].add(a[i - 2])); } Scanner in = new Scanner(System.in); while(in.hasNext()) { n = in.nextInt(); System.out.println(a[n]); } } }
发表评论
-
ACM 之 Java BigInteger
2011-06-01 20:26 0Java 的大整数类在ACM 中大有用武之地 ... -
判断点是否构成多边形, 顶点连续给出
2011-05-26 14:27 0#include <cstdio> #inc ... -
poj pku 1981 Circle and Points 点与圆 位置关系
2011-05-26 11:29 1261题目描述: http://poj.org/problem?id ... -
poj 1032 Parliament 数学
2011-05-25 17:34 1210题目描述: http://poj.org/problem?i ... -
poj 1385 Lifting the Stone 多边形重心
2011-05-25 11:13 1026题目描述: http://poj.org/problem?i ... -
poj 2676 Sudoku dfs 深搜
2011-05-16 21:05 871题目描述: http://poj.org/problem?i ... -
hdoj 2064 汉诺塔III 递推
2011-05-15 22:29 883题目描述: http://acm.hdu.edu.cn/sh ... -
hdoj 1207 汉诺塔II dp 动态规划
2011-05-15 21:22 1666题目描述: http://acm.hdu.edu.cn/sh ... -
poj 2420 A Star not a Tree? 多边形 费马点
2011-05-14 18:57 1795题目描述: http://poj.org/problem?i ... -
poj 2954 Triangle Pick 定理
2011-05-14 16:36 1082题目描述: http://poj.org/problem?i ... -
poj 1012 Joseph
2011-05-10 17:42 1230题目描述:poj.org/problem?id=10 ... -
zoj 1081 Points Within 点与多边形关系
2011-05-07 17:51 1129题目描述: http://acm.zju.edu.cn/on ... -
poj 1835 宇航员
2011-05-03 17:00 798题目描述:http://poj.org/problem?id ... -
poj 2398 Toy Storage
2011-04-23 20:19 713题目描述:http://www.poj.org/proble ... -
poj 1654 Area 多边形面积
2011-04-23 20:10 894题目描述:http://poj.org/proble ... -
poj 2318 TOYS 点 直线 位置关系
2011-04-23 10:06 663题目描述:http://poj.org/problem?id= ... -
poj pku 1673 EXOCENTER OF A TRIANGLE 三角形 垂心
2011-04-09 16:41 542题目描述:http://poj.org/problem?id= ... -
pc 111303 uva 10195 The Knights Of The Round Table
2011-04-04 16:06 750题目描述:http://www.programming-cha ... -
pc 111302 uva 10180 Rope Crisis in Ropeland!
2011-04-03 20:46 835题目描述: http://www.programming-ch ... -
poj 1971 Parallelogram Counting 平行四边形个数
2011-04-03 10:05 1212题目描述:http://poj.org/problem?id= ...
相关推荐
poj 2506 Tiling.md
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ2601 solution 题解 递推 POJ2601
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj分类poj分类poj分类poj分类
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
北大POJ2002-Squares 解题报告+AC代码
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
POJ1048,加强版的约瑟夫问题 难度中等
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
用递推方法+高精度算法,解决了poj1832 的连环锁问题,时间32ms。。。。。。
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
Poj中一些题目的源代码,里面共有二十多道题目,OI