题目描述

在你的帮助下，D和Z拼好了地图。现在，她们顺着地图上的路线向前走，面前出现了一个很长的楼梯，热爱冒险的她们当然希望继续探索。
她们发现，这个楼梯上有一些破损的阶梯，是不能踩踏的。
假设她们每次可以向上爬1级或2级或3级阶梯。
D想知道，对于给定的一种状态，有多少种方案能到达楼梯尽头。

输入

共3行。
第1行一个整数n（1≤n≤100），表示台阶数。
第2行一个整数m（1≤m≤n），表示不能踩的台阶数。
第3行m个整数，表示坏的台阶的级数（保证能走到尽头）。

输出

共1行。
一个整数，表示到尽头的方案总数。
友情提示：答案在int64范围内。

思路

递推求解，先手动判断前3个然后f[i]=f[i−1]+f[i−2]+f[i−3]

#include 
using namespace std;
long long a[105],f[105];
int n,m;
int main()
{
    freopen("stairs.in", "r", stdin);
    freopen("stairs.out", "w", stdout);
    int x;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        scanf("%d",&x);
        f[x]=1;
    }

    if (f[1]!=1) a[1]=1; else a[1]=0;
    if (f[2]!=1) a[2]=a[1]+1; else a[2]=0;
    if (f[3]!=1) a[3]=a[2]+a[1]+1; else a[3]=0;
    for (int i=4;i<=n;i++)
        if (f[i]!=1)
            a[i]=a[i-1]+a[i-2]+a[i-3];
    printf("%lld\n",a[n]);
    return 0;
}