3531. 定西

开始时，将所有broken steps标记为0，为不可走
dp[0] = 1 // 标记起点，可走

状态转移方程：
if dp[i] == 0
dp[i] = 0 // this is broken step
else
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] // i - 3 >= 0

题目大意

题面很好理解，传送门

思路分析

爬楼梯，典型递归或者DP
这道题我用的DP

边界条件：dp[0] = 1 表示从楼梯底部出发
特判 dp[2] = dp[1] + 1;
动态转移方程:dp[i] = dp[i-1]+dp[i-2]+dp[i-3] (i>=3)

具体代码

#include<bits/stdc++.h>
using namespace std;
int f[110] = {0};
int dp[110] = {0};
int main(){
    int n,k;
    cin >> n >> k;
    while(k){
        k--;
        int temp;
        cin >> temp;
        f[temp] = -1; //标记坏掉的楼梯
        dp[temp] = 0; //不能走
    }
    dp[0] = 1;
    if(f[1] != -1) dp[1] = 1;
    if(f[2] != -1)  dp[2] = dp[1] + 1;
    for(int i = 3; i <= n; i++){
        if(f[i] != -1){ //如果楼梯能到达
            dp[i] = dp[i-1]+dp[i-2]+dp[i-3];
        }
    }
    cout << dp[n] << endl;
    return 0;
 }

本来还有些担心，因为长整型只能表示到70阶左右，没想到跑完案例尽然AC了

也可递归判断。代码参考博客https://blog.csdn.net/liu16659/article/details/103823470

include

using namespace std;

const int maxn = 1e3;
int a[maxn];
int dp[maxn];
int main()
{
int n,k;
cin >> n >> k;
memset(a,0,sizeof(a));
dp[0] = 1;
dp[1] = 1;
dp[2] = 2;
for(int i = 0; i < k; ++i){
int tmp;
cin >> tmp;
a[tmp] = 1;
}
for(int i = 1; i <= n; ++i){
if(a[i] == 1)
dp[i] = 0;
else
dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
}
cout << dp[n] << endl;
return 0;
}

//刚开始也是被用例4搞蒙了，才发现台阶n也能坏，相当于没有办法上去，答案为0

include

include

using namespace std;

int main()
{
int n, k;
scanf(“%d%d”, &n, &k);
vector v(n + 1);
for(int i = 0; i <= n; i++)
{
if(i == 0)
v[i] = 1;
else{
v[i] = 0;
}
}
for(int i = 0; i < k; i++)
{
int x;
scanf(“%d”, &x);
v[x] = -1;
}
for(int i = 1; i <= n; i++)
{
if(v[i] == -1) continue;
if(i - 1 >= 0 && v[i - 1] != -1)
{
v[i] += v[i - 1];
}
if(i - 2 >= 0 && v[i - 2] != -1)
{
v[i] += v[i - 2];
}
if(i - 3 >= 0 && v[i - 3] != -1)
{
v[i] += v[i - 3];
}
}
if(v[n] == -1) printf(“0”);
else{
printf(“%d”,v[n]);
}
return 0;
}

int main()
{
int N, K;
cin >> N >> K;
bool damaged[110] = { 0 }; //记录损坏的台阶
int count[110] = { 0 }; //到达每个台阶的走法
int temp;

for (int i = 0; i < K; i++)
{
    scanf("%d", &temp);
    damaged[temp] = true;
}

count[0] = 1;   //从0开始走，给0赋初值1
for (int i = 1; i <= N; i++)
{
    if (damaged[i] == false)    //如果楼梯没坏
    {
        if (i == 1)
        {
            count[i] += count[i - 1];
        }
        else if (i == 2)
        {
            count[i] += count[i - 1] + count[i - 2];
        }
        else
        {
            count[i] += count[i - 1] + count[i - 2] + count[i - 3];
        }
    }
}

printf("%d\n", count[N]);
return 0;

}

有哪位路过的大师提供一些思路

case 4中存在输出为0的情况

状态转移方程 ：dp[i] = dp[i + 1] + dp[i + 2] + dp[i + 3];

const int maxn = 105;
long long dp[maxn] = { 0 }, HashTable[maxn] = { 0 }; //HashTable记录台阶的好坏 0为好-1为坏，
int main() { //dp 记录当前台阶到最终台阶的步数
int n, k;
cin >> n >> k;
while (k–) {
int x;
cin >> x;
HashTable[x] = -1;
}
if (HashTable[n] == -1) {
cout << “0”;
return 0;
}
dp[n] = 1;
for (int i = n-1; i >= 0; i–) {
if (HashTable[i] == -1) {
dp[i] = 0; //坏台阶时候 dp为0
continue;
}
dp[i] = dp[i + 1] + dp[i + 2] + dp[i + 3];
}
cout<<dp[0];
return 0;
}

直接搜索吧，水题可以不用dp

深度遍历算法

include

include

using namespace std;
int n,k,cnt=0;
set s;
void dfs(int x){
if(s.find(x)!=s.end()||x>n) return;
if(x==n){
cnt++;
return;
}
dfs(x+1);
dfs(x+2);
dfs(x+3);
}
using namespace std;
int main(){
scanf(“%d%d”,&n,&k);
for(int i=0;i<k;i++){
int tem;
scanf(“%d”,&tem);
s.insert(tem);
}
dfs(0);
printf(“%d”,cnt);
return 0;
}

记得特判最后一级可能是坏的。。。。。。

//AC代码

include

using namespace std;
int count=0;
int a[110];
int Isgood(int index,int k){
int i;
for(i=0; i<k; i++){
if(index==a[i]){
return 0;
}
}
if(i==k)
return 1;
}
void Upst(int index,int k,int n){
if(index==n){ //递归出口
count++;
return ;
}
if(Isgood(index+1,k)&&index+1<=n) //一定要判断走完后不超过n
Upst(index+1,k,n);
if(Isgood(index+2,k)&&index+2<=n)
Upst(index+2,k,n);
if(Isgood(index+3,k)&&index+3<=n)
Upst(index+3,k,n);
}
int main(){
int n,k;
int i;
cin>>n>>k;
for(i=0; i>a[i];
}
Upst(0,k,n);
cout<<count<<endl;
return 0;
}

额，原来最后一阶如果是坏的就认为不能完成

开始还以为是爬到最高一阶。。。结果看到case 4才知道这个点。

include

include

include

include

using namespace std;

struct Steps
{
int route;
bool broke;
};

int main()
{
struct Steps steps[101];
memset(steps, 0, sizeof(struct Steps)*101);
int N, K;
cin>>N>>K;
int k;
for(k = 0; k < K; k++)
{
int temp;
cin>>temp;
steps[temp].broke = true;
}
int n;
steps[0].route = 1;
for(n = 1; n <= N; n++)
{
if(steps[n-1].broke == false) steps[n].route += steps[n-1].route;
if(n >= 2&&steps[n-2].broke == false) steps[n].route += steps[n-2].route;
if(n >= 3&&steps[n-3].broke == false) steps[n].route += steps[n-3].route;
}
if(steps[N].broke == false) cout<<steps[N].route<<endl;
else cout<<0<<endl;
return 0;
}

借鉴一楼大佬的
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
int i;
int a[n + 1];
// 将每个字节设置为1，此时每个int元素为16843009 = 0x1010101
memset(a,1,sizeof(a));
int tmp;
a[0]= 1;
for(i = 0; i < k; i++){
cin >> tmp;
a[tmp] = 0;
}
for(i = 1; i < n + 1; i++){
if(a[i] == 0){
a[i] = 0;
}else{
if(i == 1){
a[i] = a[i -1];
}else if(i == 2){
a[i] = a[i - 1] + a[i - 2];
}else{
a[i] = a[i - 1] + a[i - 2] + a[i - 3];
}
}
}
cout << a[n] << endl;
return 0;
}