5.小华爬泰山

视频讲解：小华爬泰山_哔哩哔哩_bilibili

解题思路：

1. 在爬楼梯的基础上设置了陷阱，那么在每一次计算当前楼梯的方案数的前提下，一定要判断这个楼梯是否是陷阱，如果是陷阱，则方案数为0，而不能在全部计算完以后才将m个阶梯的方案数设为0（想想为什么）？

2.接下来就是处理陷阱楼梯，可以使用打标记的方案，设置一个布尔数组，将陷阱的楼梯全部标记为1，方便步骤1的判断

3.解决初始化的问题，一步可以上1级，2级，3级楼梯，那么上第一级台阶的方案数为1，第二级的方案数为2，第3级的方案数为4（1,1,1,1），（2,1），（1,2），（3）种，在这里要想一下，如果陷阱台阶出现在这三个初始化的台阶上的时候会有什么情况呢？

4.特殊判断：

（1）当第一级台阶是陷阱的话，dp[1]=0;

（2）当第二级台阶是陷阱的话，dp[2]=0;

（3）当第一级台阶是陷阱，第二级不是的时候，dp[1]=0,dp[2]=1;

（4）当第三级台阶是陷阱的话，dp[3]=0;

（5）当第一级不是陷阱，第二不是陷阱，第三不是陷阱的话dp[3]=4;

（6）当第一级是陷阱，第二不是陷阱，第三不是陷阱的话dp[3]=2;

（7）当第一级不是陷阱，第二级是陷阱的话，第三不是陷阱的话dp[3]=2；

（8）当第一阶是陷阱，第二级是陷阱，第三不是陷阱的话dp[3]=1；

   至此，初始化完成。

5，接下来就是挨个判断以后的台阶

#include<bits/stdc++.h>
using namespace std;
bool flag[5000];
const int mod=100003;
long long dp[5000]; 
int main()
{int n,m,x;cin>>n>>m;for(int i=1;i<=m;i++){cin>>x;flag[x]=1;//表示x号楼梯是陷阱 }dp[1]=1;//初始化 dp[2]=2;dp[3]=4;if(flag[1]==1)//如果台阶1是陷阱 {dp[1]=0;//台阶1方案数为0 if(flag[2]==1)//如果台阶2也是陷阱 {dp[2]=0;//台阶2的方案数为0 dp[3]=1;//台阶3的方案数为1 }else//如果台阶2不是陷阱的话 {dp[2]=1;//台阶2的方案数为1 dp[3]=2;//台阶3的方案数为2 }}else//如果台阶1不是陷阱的话 {if(flag[2]==1)//如果台阶2是陷阱{dp[2]=0;//台阶2的方案数为0 dp[3]=2;//台阶3的方案数为2 }}if(flag[3]==1)//如果台阶3是陷阱 dp[3]=0;//台阶3的方案数为0 for(int i=4;i<=n;i++){if(flag[i]!=1)dp[i]=(dp[i-1]%mod+dp[i-2]%mod+dp[i-3]%mod)%mod;}if(dp[n]==0)cout<<-1;elsecout<<dp[n];return 0;
}