NOIOJ 取数游戏

题目描述

我们来玩一个游戏:自然数1到N,按顺序列成一排,你可以从中取走任意个数,但是相邻的两个不可以同时被取走。如果你能算出一共有多少种取法,那么你会被天神Lijiganjun奖励。

输入

仅包含一个数n(1< n < 50)。

输出

仅包含一个数———你的答案。

样例输入

5

样例输出

13

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//开Long long,要不最后一个点过不去

#include<iostream>
#include<cstring>
using namespace std;
long long f[100];
long long fib(long long t){
    if(t==1||t==2)return 1;
    if(f[t]!=-1)return f[t];
    f[t]=fib(t-1)+fib(t-2);
    return f[t];
}
int main(){
    long long a;
    cin>>a;
    memset(f,-1,sizeof(f));
    cout<<fib(a+2);
}

发表评论

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