骨牌铺方格
Problem Description
在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格,输入n ,输出铺放方案的总数.
例如n=3时,为2× 3方格,骨牌的铺放方案有三种,如下图:
Input
输入数据由多行组成,每行包含一个整数n,表示该测试实例的长方形方格的规格是2×n (0<n<=50)。
Output
对于每个测试实例,请输出铺放方案的总数,每个实例的输出占一行。
Sample Input
Sample Output
Author
lcy
Source
Recommend
lcy
只要简单的推断即可~
假设用arr[i]表示2*i的方格一共有组成的方法数,我们知道arr[1]=1;arr[2]=2;
现在假设我们已经知道了arr[i-1]和arr[i-2],求arr[i],所谓arr[i],不过是在2*(i-1)的格子后边加上一格2*1的方格罢了,骨牌在这一格上横着放,竖着放,如果前面i-1块已经铺好,则第i块只有一种铺法,就是竖着放,如果要横着放,也只有一种铺法,不过要求前面i-2块已经铺好!
因此arr[i]=arr[i-1]+arr[i-2];
还有数字可能会很大,用64位,我32位的交了几次都没有通过!
#include<iostream>
using namespace std;
int main()
{
__int64 arr[51];
int num;
arr[1]=1;arr[2]=2;
for(int i=3;i<=50;i++)
arr[i]=arr[i-1]+arr[i-2];
while(scanf("%d",&num)!=EOF)
{
printf("%I64d\n",arr[num]);
}
return 0;
}
分享到:
相关推荐
杭电oj1000题解题报告
杭电OJ题目分类的叙述,可以方便去学习去做。
杭电OJ 2028代码 the rosolve of the hdu 2028
杭电oj 1047习题
本资源主要提供了杭电oj题目分类和自测状况两大类 可实现随机选题等功能.
杭电OJ(1000-1099) AC 代码
杭电OJ部分威士忌的代码 杭电OJ部分威士忌的代码杭电OJ部分威士忌的代码
杭电oj上的一些疑问,适用于初学者,可以解答一些疑问 都是一些水题
杭州电子科技大学 oj离线版
杭电oj分类
这是HDUOJ上面的140道题目的答案,其中大部分都是简单题,有些太简单的就没有收集进去,代码为C/C++,全都AC了的,其中有些有具体的说明是怎么做的,例如博弈论那些
课程资源 杭电OJ1000-1099答案 ,仅供参考...
杭电oj的离线版以及题目分类的文档 更加一目了然 方便选择适合的题目做 适合暂时上不了网的用于练习
这是杭电oj入门100题的题号,通过这100题可以掌握基本输入输出操作,及基本算法
杭电离线oj(2010版),方便不能上网的朋友用,比别的版本增加了很多题!
这是杭电OJ上某些题的解题报告,后续还有上传很多!
基于Laravel 5.0的OJ题解网站 , 目前涵盖安科OJ,南阳OJ,杭电OJ ,北大OJ,浙大OJ.zip
杭电oj1048答案,c++代码,适合初学者,思路简单