题解 AT4787 【[ABC129C] Typical Stairs】

houpingze

指正翻译

应该是

有 n 级台阶，有 m 级台阶不能走，分别为a_1,a_2...a_m级台阶。

思路：

由于

每次可以向上一格或两格

所以当我们在第i个台阶的时候[链接登录后可见]$，我们可能从i-1级跳上去，也有可能从i-2级跳上去

code:

/*
边界：
	f[0]=1,f[1]=1;
递推式：
	f[i]=(f[i-1]+f[i-2])%MOD;
特殊情况：
	如果此条路被破坏，解的总数为0 
解：
	f[n]  
*/

#include<bits/stdc++.h> 
#define MOD 1000000007
using namespace std; 
int n,cnt,m,a[114514],ans,tmp;
int f[1919810];
/*
	a[i]的值如果为1，表示此条路被破坏，走不通
	否则，可以走通 
*/
int main() { 
	cin>>n>>m;
	while(m--) cin>>tmp,a[tmp]=1;//标记，tmp这条路被破坏 
	if(!a[0]) f[0]=1;//注意判断第0条路是否被破坏 
	if(!a[1]) f[1]=1;
	for(int i=2;i<=n;i++) 
		if(!a[i]) //!a[i]也就是a[i]==0，判断是否被破坏 
			f[i]=(f[i-1]+f[i-2])%MOD; 
	cout<<f[n]<<endl;//解就是f[n] 
    return 0;
}