P1255 数楼梯
题目描述
楼梯有N阶,上楼可以一步上一阶,也可以一步上二阶。
编一个程序,计算共有多少种不同的走法。
输入输出格式
输入格式:
一个数字,楼梯数。
输出格式:
走的方式几种。
输入输出样例
输入样例#1: 复制
4
输出样例#1: 复制
5
说明
用递归会太慢,需用递推
(60% N<=50 ,100% N<=5000)
思路:数学+高精
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
struct nond{
int num[];
}f[];
void jia(int pos){
f[pos].num[]=max(f[pos-].num[],f[pos-].num[]);
for(int i=;i<=f[pos].num[];i++)
f[pos].num[i]=f[pos-].num[i]+f[pos-].num[i];
for(int i=;i<=f[pos].num[];i++)
if(f[pos].num[i]>=){
if(i==f[pos].num[]) f[pos].num[]++;
f[pos].num[i+]+=;
f[pos].num[i]%=;
}
for(;f[pos].num[]>=;f[pos].num[]--) if(f[pos].num[f[pos].num[]]) break;
}
int main(){
scanf("%d",&n);
if(n==){ cout<<"";return ;}
f[].num[]=f[].num[]=f[].num[]=f[].num[]=;
for(int i=;i<=n;i++) jia(i);
for(int i=f[n].num[];i>=;i--) cout<<f[n].num[i];
}