洛谷题目传送门 | AT原题传送门
思路
这其实是一道递推题。
打眼一看，这道题和P1255 数楼梯是差不多的，只不过是本题又新增了一个条件：有 mm 个楼梯是坏的。
如果没有这个条件，我们可以定义，第 ii 阶楼梯的总方案数为 fif_i，从题目中可以很容易得出：fi=fi−1+fi−2(i≥2)f_i=f_{i-1}+f_{i-2}(i \geq 2)，因为只能从第 i−1i-1 和第 i−2i-2 阶楼梯上到第 ii 阶楼梯。
加上那个条件后，我们可以定义一个 bool\texttt{bool} 数组 vis\texttt{vis}，如果第 ii 阶楼梯是坏的，那 visi=truevis_i=true，否则 visi=falsevis_i=false。
有几点需要注意：
- 每次递推都需 mod 109+7\bmod 10^9+7；
- 如果连续两阶楼梯都是坏的，也就是 visi=truevis_i=true 且 visi−1=truevis_{i-1}=true，直接输出 00 并退出程序（不判断也不会超时）；
- 从第 00 阶台阶开始计算；
- 赋 f0f_0 和 f1f_1 的初始值时要特判第 00 和第 11 阶楼梯是否损坏。
直接上代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #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;
}
|
记得结尾要换行哦
