洛谷 AT4787 题解

洛谷题目传送门 | AT原题传送门

思路

这其实是一道递推题。

打眼一看，这道题和P1255 数楼梯是差不多的，只不过是本题又新增了一个条件：有 $m$ 个楼梯是坏的。

如果没有这个条件，我们可以定义，第 $i$ 阶楼梯的总方案数为 $f_i$，从题目中可以很容易得出：$f_i=f_{i-1}+f_{i-2}(i \geq 2)$，因为只能从第 $i-1$ 和第 $i-2$ 阶楼梯上到第 $i$ 阶楼梯。

加上那个条件后，我们可以定义一个 $\texttt{bool}$ 数组 $\texttt{vis}$，如果第 $i$ 阶楼梯是坏的，那 $vis_i=true$，否则 $vis_i=false$。

有几点需要注意：

1. 每次递推都需 $\bmod 10^9+7$；
2. 如果连续两阶楼梯都是坏的，也就是 $vis_i=true$ 且 $vis_{i-1}=true$，直接输出 $0$ 并退出程序（不判断也不会超时）；
3. 从第 $0$ 阶台阶开始计算；
4. 赋 $f_0$ 和 $f_1$ 的初始值时要特判第 $0$ 和第 $1$ 阶楼梯是否损坏。

直接上代码

#include<cstdio>
#include<iostream>
using namespace std;
inline int read()//快读
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0' && ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
const int mod=1e9+7;
int n,m,a,f[100010];
bool vis[100010]={0};
int main()
{
	n=read();m=read();
	for(int i=1;i<=m;i++)
	{
		a=read();
		vis[a]=1;//标记该台阶已损坏
		if(vis[a] && vis[a-1])//判断是否有连续两个台阶是坏的
		{
			cout<<0<<endl;
			return 0;
		}
	}
	if(!vis[0])//特判第0和第1阶楼梯是否损坏
	{
		f[0]=1;
	}
	if(!vis[1])
	{
		f[1]=1;
	}
	for(int i=2;i<=n;i++)
	{
		if(vis[i]) f[i]=0;//如果该楼梯损坏，则无法上到该楼梯
		else
		{
			f[i]=(f[i-1]+f[i-2])%mod;//递推式(不要忘了取模)
		}
	}
	cout<<f[n]<<endl;
	return 0;
}

记得结尾要换行哦