洛谷P1720 月落乌啼算钱 题解

题目传送门

初看题目，好难。再看一次，探索规律，发现这就是有名的斐波那契数列。

F[i]=f[i-1]+f[i-2]

SO 代码很简单，貌似要开long long，又貌似不用开。

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
ll n,pre[50]={0,1,1};
int main(){
    for(int i=3;i<=48;i++) pre[i]=pre[i-1]+pre[i-2];
    scanf("%lld",&n);
    printf("%lld.00
",pre[n]);
    return 0;
}
/* 1 1 2 3 5 8 
   1 2 3 4 5 6*/
//请自动屏蔽↑