问题标题: 酷町堂：2752 爬楼梯

题目描述 Description

小明和同学们顺利闯过了第二关，进入第三关的时候，小明和同学们发现了一个楼梯，可是有些楼梯坏了。智慧之门门主说，只要同学们通过这个楼梯就可以游玩里面的项目，可是同学们必须为我解决一个问题，这个时候大家都迫不及待的让智慧之门门主快点说问题。智慧之门门主指着面前的楼梯说，你可以一步一级，或一步二级，也可以一步三级，但是某些台阶是坏的，即脚不能踩在上面，哪位同学能求出登上最高台阶的总方案数。小明和同学在思考？

输入描述 Input Description

第一行两个整数，第一个数为楼梯总级数n（n<50），第二个数表示有几个坏台阶m
第二行连续m个整数为坏台阶的级数。注意：数据的规模在longint范围内。

输出描述 Output Description

一个整数，表示登上最高台阶的方案数

样例输入 Sample Input

7 2

4 6

样例输出 Sample Output

6

样例过了，WA0

#include<bits/stdc++.h>
#include<iostream>
#pragma GCC optimize(3)
using namespace std;
int n,m,a[55],f[55],b[105];
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
    	cin>>a[i];
    	b[a[i]]=1;
	}
	f[1]=1;
	f[2]=2;
	f[3]=4;
	for(int i=4;i<=n;i++){
		if(!b[i]){
			f[i]=f[i-1]+f[i-2]+f[i-3];
		}else{
			f[i]=0;
		}
	}
	cout<<f[n];
    return 0; 
}

汪恺恒在2021-02-20 09:20:24追加了内容

高精代码

#include<bits/stdc++.h>
#include<iostream>
#pragma GCC optimize(3)
using namespace std;
long long n,m,s;
string f[105];
int a[10005],b[10005],c[10005];
string Plus(string x,string y){
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	memset(c,0,sizeof(c));
	a[0]=x.length(),b[0]=y.length();
	c[0]=max(a[0],b[0]);
	for(int i=1;i<=a[0];i++){
		a[i]=x[a[0]-i]-'0';
	}
	for(int i=1;i<=b[0];i++){
		b[i]=y[b[0]-i]-'0';
	}
	int jw=0;
	for(int i=1;i<=c[0];i++){
		c[i]=a[i]+b[i]+jw;
		jw=c[i]/10;
		c[i]%=10;
	}
	if(jw!=0){
		c[0]++;
		c[c[0]]=jw;
	}
	string ans="";
	for(int i=c[0];i>=1;i--){
		ans+=char(c[i]+'0');
	}
	return ans;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
    	cin>>s;
    	f[s]='0';
	}
	if(f[1]=="") f[1]="1";
	if(f[2]=="") f[2]="2";
	if(f[3]=="") f[3]="4";
	for(int i=4;i<=n;i++){
		if(f[i]==""){
			f[i]=Plus(f[i-1],Plus(f[i-2],f[i-3]));
		}
	}
	cout<<f[n];
    return 0; 
}

汪恺恒在2021-02-20 09:23:01追加了内容

发现一个BUG，但还是WA40

#include<bits/stdc++.h>
#include<iostream>
#pragma GCC optimize(3)
using namespace std;
long long n,m,s;
string f[105];
int a[10005],b[10005],c[10005];
string Plus(string x,string y){
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	memset(c,0,sizeof(c));
	a[0]=x.length(),b[0]=y.length();
	c[0]=max(a[0],b[0]);
	for(int i=1;i<=a[0];i++){
		a[i]=x[a[0]-i]-'0';
	}
	for(int i=1;i<=b[0];i++){
		b[i]=y[b[0]-i]-'0';
	}
	int jw=0;
	for(int i=1;i<=c[0];i++){
		c[i]=a[i]+b[i]+jw;
		jw=c[i]/10;
		c[i]%=10;
	}
	if(jw!=0){
		c[0]++;
		c[c[0]]=jw;
	}
	string ans="";
	for(int i=c[0];i>=1;i--){
		ans+=char(c[i]+'0');
	}
	return ans;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
    	cin>>s;
    	f[s]="0";
	}
	if(f[1]=="") f[1]="1";
	if(f[2]=="") f[2]="2";
	if(f[3]=="") f[3]="4";
	for(int i=4;i<=n;i++){
		if(f[i]==""){
			f[i]=Plus(f[i-1],Plus(f[i-2],f[i-3]));
		}
	}
	cout<<f[n];
    return 0; 
}

汪恺恒在2021-02-20 14:27:04追加了内容

d

汪恺恒在2021-02-20 19:47:05追加了内容

d