夏令营-dp-ACM-dp-axuhongbo的个人博客

单点时限: 1.0 sec

内存限制: 256 MB

这么多年你一个人一直在走
方向和天气的节奏会让你忧愁
你说你遇见了一大堆奇怪的人
他们看上去好像都比你开心
——李志《定西》

这首歌的吉他节奏总感觉是在致敬《加州旅馆》，前奏又像葫芦娃里面在蛇精洞是的配乐

一个人走走了很多年，发现自己走到了一个很长的，年久失修的楼梯面前。年久失修的意思就是，有 k 个台阶坏了，没法走。

楼梯一共有 n 层，你一次能上一阶、两阶或三阶台阶，请问，你从楼梯底部 (0 开始) 走到楼梯顶部，共有多少种走法。

输入数据共两行，第一行包含两个自然数 n (1≤n≤100) 和 k (0≤k<n)，第二行包含 k 个自然数 Xi (1≤Xi≤n)，数字之间用一个空格隔开，表示损坏的台阶的序号（从楼梯底部到楼梯顶部，台阶序号依次为 1 到 n）。

输出数据仅包含一个整数，表示所有可行走法的总数。

input
5 2
2 4
output
2

D. 定西

动态规划基础（水）题。坏掉的台阶走法数固定为0，判断一下即可。

#include <bits/stdc++.h>

using namespace std;

int main()

{

int n, b, w[101], dp[101], cnt=0;

cin>>n>>b;

for(int i=0; i<b; i++) cin>>w[i];

if(w[cnt]==1) {dp[1]=0; cnt++;} else dp[1]=1;

if(w[cnt]==2) {dp[2]=0; cnt++;} else dp[2]=1+dp[1];

if(w[cnt]==3) {dp[3]=0; cnt++;} else dp[3]=1+dp[1]+dp[2];

for(int i=4; i<=n; i++)

{

if(w[cnt]==i) {dp[i]=0; cnt++;}

else dp[i]=dp[i-1]+dp[i-2]+dp[i-3];

}

cout<<dp[n];

return 0;

}