题目描述
楼梯有 NN 阶，上楼可以一步上一阶，也可以一步上二阶。
编一个程序，计算共有多少种不同的走法。
输入格式
一个数字，楼梯数。
输出格式
输出走的方式总数。
输入输出样例
输入 #1复制
4
输出 #1复制
5
说明/提示
- 对于 60\%60% 的数据，N \leq 50N≤50；
- 对于 100\%100% 的数据，N \leq 5000N≤5000。
分析:
说实话这题我真的快写吐了,刚拿到的时候,开心的一批,递推第一篇第一题,这么水的吗,不禁想起当年初次接触acm,室友从cf上选了几道题给我们做,当时这个题难得我半天想不通透,如今再见此题,看我不将你灭的体无完肤,一波撸代码,提交,走你!
我kiao?!!wa?我惊了,不会吧,这题都能wa?又改了改,还是wa...不禁陷入思考人生的境地
思考完了,看看题解吧...果然,题还是那个题,只是范围大了,5000,已经不是普通int能承受的范围了,还是要高精啊.....
撸一波高精代码...开数组200,事实证明我还是太年轻了,200根本不够看的好吗?!不多说,直接开6000数组
90分,其中一个数据死活过不去,真的要崩溃了.....下载数据下来看看吧....
mdzz,n=0.....果然是我年轻了,浪费了一次下载数据的机会...
上AC代码:
#include<iostream>#include<string.h>
using namespace std;
int a[5005][6005];
int n;
void add(int i,int j);
int main()
{memset(a,0,sizeof(a));cin>>n;a[0][1]=0;a[1][1]=1;a[2][1]=2;for(int i=3;i<=n;i++)add(i-1,i-2);if(n==0)cout<<0;else{for(int k=n;k<=n;k++){int i=6000;//cout<<k<<": ";while(a[k][i]==0)i--;for(;i>=1;i--)cout<<a[k][i];cout<<endl;}}return 0;
}
void add(int i,int j)
{int t=1;int cf=0;while(t<6000){int temp=a[i][t]+a[j][t]+cf;cf=temp/10;temp=temp%10;a[i+1][t]=temp;t++;}if(cf>0)a[i+1][t]=cf;//cout<<"a is "<<a[i+1][3]<<a[i+1][2]<<a[i+1][1]<<endl;
}