当前位置: 代码迷 >> 综合 >> HDU-2046 骨牌铺方格
  详细解决方案

HDU-2046 骨牌铺方格

热度:69   发布时间:2023-11-25 21:09:35.0

此类题给出信息很少,如我一般的小白根据题目描述可以将此类题归为规律题,由骨牌大小1X2,知骨牌竖着放占1个横向单位,横着放占两个单位,由此可将其看做两种不同的情况,N = 3时,可看做为N=2的基础上加一个可竖着放骨牌的横向单位,同时也可看作为N=1的基础上加两个横向单位(即横着放的骨牌),两种情况的和构成N = 3时的解,推出递推公式f(n)=f(n-1)+f(n-2);注意一下虽然只算50组,但结果INT型装不下,改用long long型数组。

#include<iostream>
using namespace std;
int main()
{int n;long long a[100];a[1] = 1;a[2] = 2;for(int i=3; i<=50; i++){a[i] = a[i-1]+a[i-2];}while(cin>>n){cout<<a[n]<<endl;}return 0;
}