hdu-2563
2024-09-30 00:50:05
统计问题
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 8724 Accepted Submission(s): 5171Problem Description在一无限大的二维平面中,我们做如下假设:
1、 每次只能移动一格;
2、 不能向后走(假设你的目的地是“向上”,那么你可以向左走,可以向右走,也可以向上走,但是不可以向下走);
3、 走过的格子立即塌陷无法再走第二次;求走n步不同的方案数(2种走法只要有一步不一样,即被认为是不同的方案)。
Input首先给出一个正整数C,表示有C组测试数据
接下来的C行,每行包含一个整数n (n<=20),表示要走n步。Output请编程输出走n步的不同方案总数;
每组的输出占一行。Sample Input212Sample Output37
这是一道递归问题,首先我们要求出它的递归公式。。
我们设向上走的步数为a[i],向左和右走的步数为b[i]。
则a[i]=a[i-1]+b[i-1];
b[i]=a[i-1]*2+b[i-1];(因为有左上和右上两种方向)
化简得:
f[i]=2*f[i-1]+f[i-2]
AC代码:
#include<bits/stdc++.h>
using namespace std; int a[]; int main(){
int c,n;
cin>>c;
while(c--){
cin>>n;
a[]=;
a[]=;
for(int i=;i<=;i++){
a[i]=a[i-]*+a[i-];
}
cout<<a[n]<<endl;
}
return ;
}
最新文章
- 利用Python【Orange】结合DNA序列进行人种预测
- Linux cp (复制)命令简介
- web自学网站
- hdu 5291 dp+优化 ****
- jquery delay()介绍及使用指南
- 修改SQL Server 2005 数据库文件名字
- 解决Android SDK Manager 更新、下载慢以及待安装包列表不显示
- Hadoop学习笔记1---简介 优点 架构分析
- memcache分布式部署的原理分析
- 用caffe给图像的混乱程度打分
- discuz相关总结
- Concurrency Is Not Parallelism (Rob pike)
- JAVA面向对象-----封装
- masm下几种常见函数调用方式
- Maven学习(六)-- Maven与Eclipse整合
- go源文件中是否有main函数
- USB插入电脑的硬件检测和枚举流程
- codevs1735 方程的解数(meet in the middle)
- 【python学习-4】可复用函数与模块
- windows中cmd--->;进入到别的磁盘
热门文章
- VS2012+Win7站点公布具体步骤
- C#文件操作与编程
- GuozhongCrawler系列教程 (1) 三大PageDownloader
- 求两个有序数组的中位数(4. Median of Two Sorted Arrays)
- 5分钟快速入门Markdown
- MySQL 导入导出命令(转载)
- sql server t-sql脚本转成oracle plsql
- EasyRTMP实现Demux解析MP4文件进行rtmp推送实现RTMP直播功能
- 安装DotNetCore.1.0.1-VS2015Tools.Preview2.0.3引发的血案
- 如何设置SVN提交时必须输入注释