【2016.10.6NOIP普及模拟】Stairs

发布于 2019-04-11  16 次阅读


题目描述

在你的帮助下,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[i1]+f[i2]+f[i3]

#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;
}
]]>