杭电acm 2046 骨牌铺方格

2009-12-04 14:49

PS:依然递推题…我依然很笨…无语,见分析:
从图中也可以观察出来,第N张牌的排列可以又N-1张牌的排列再在末尾加上一张竖的牌。这样依然合法。
也可以在N-2张合法排列的牌后面加上两张横着放的牌(如果竖着放就和上面一种重复了)。
所以f(n) = f(n-1) + f(n-2)
即又是一个斐波那契数列。
注意用数组,还要用64位整数。

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

    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注