洛谷的题目名称越来越瞎叉叉乱写了

思路

---

这道题看上去很高大上，但实际上一看（偷偷翻算法书）就知道这是某数列的通项公式（作为一个OIer，这是基本的数学素养，不懂者......退役吧）。

既然知道是斐波那契数列，那么，脱口而出：F(n)=F(n-1)+F(n-2),那么恭喜您，退役吧（这就是本蒟蒻的最初想法），为什么不行呢？大家构建一下递归树（栈）就知道了，递归层数本身会栈溢出不说，光是时间复杂度，和直接拿题目给的公式模拟的时间复杂度相当了，大约是O(nn),也就是说，您成功的吧O(n)的水题变成了NP完全问题，那么正解是什么呢？

其实注意一下题目的分类——递推，便可知道正解：F[n]=F[n-1]+F[n-2]，看上去没什么区别对吗？那么恭喜您又可以退役了（非专业人士请走开），这样直接将时间降为线性，将空间也降为线性，但是，这是DP的思想，违背了题目的初衷（虽然已经能AC）：递归，况且也不是最好的算法，所以——还需要优化。时间已降为线性，再要减也可以，但要用斐波那契堆，过于复杂，不展开了（不会），但空间可以降为O(1)——运用递推。

不多废话了，上代码（真正的程序员跟他讲解再多都没有直接上代码直观）。

Code

---

#include
    
     using namespace std;long long a=1,b=1,c=0;///因为n<=48,所以大一点,用long longint n,i;int main(){    cin>>n;    for (i=3;i<=n;i++)    {        c=a+b;        a=b;        b=c;    }    cout<
     
      <<".00";///".00"是为了符合题意.......    return 0;}
     
    

后记

等我学会斐波那契堆后再来继续优化吧，时间复杂度应该是可以降为O(log2n).