洛谷 P1255 数楼梯
2024-08-24 09:26:08
题目描述
楼梯有N阶,上楼可以一步上一阶,也可以一步上二阶。
编一个程序,计算共有多少种不同的走法。
输入输出格式
输入格式:
一个数字,楼梯数。
输出格式:
走的方式几种。
输入输出样例
说明
用递归会太慢,需用递推
(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];
}
最新文章
- effective OC2.0 52阅读笔记(六 块与大中枢派发)
- 微信OAuth2.0网页授权
- [原创工具] ListView 调色盘 (Free)
- [LintCode] Pow(x, n) 求x的n次方
- ios沙盒路径
- BZOJ 2331 地板
- HDU 1312 Red and Black --- 入门搜索 DFS解法
- shutdown 和closesocket
- Android Studio快速开发之道(各种语法糖)
- java转义字符
- final、抽象类、接口、多态、
- CSS background 属性 总结
- tiny210移植linux内核(3.0.8)杂项
- Add Two Numbers 2015年6月8日
- UOJ #460 新年的拯救计划
- 「雅礼集训 2017 Day5」矩阵
- Mave------pom.xml标签详解
- jQeury 批量删除
- jenkins+sonarQube代码质量扫描 并排除指定的目录
- squid代理允许FTP访问设置