HDU 2563 统计问题 (递推)
2024-08-31 17:02:18
A - 统计问题
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d
& %I64u
Submit Status
2563
id=27335" class="ui-button ui-widget ui-state-default ui-corner-all ui-button-text-only" style="display:inline-block; position:relative; padding:0px; margin-right:0.1em; vertical-align:middle; overflow:visible; text-decoration:none; font-family:Verdana,Arial,sans-serif; font-size:1em; border:1px solid rgb(211,211,211); background-color:rgb(227,228,248); color:rgb(85,85,85)">Practice
HDU2563
Description
在一无限大的二维平面中。我们做例如以下如果:
1、 每次仅仅能移动一格。
2、 不能向后走(如果你的目的地是“向上”。那么你能够向左走,能够向右走,也能够向上走。可是不能够向下走);
3、 走过的格子马上塌陷无法再走第二次;
求走n步不同的方案数(2种走法仅仅要有一步不一样,即被觉得是不同的方案)。
1、 每次仅仅能移动一格。
2、 不能向后走(如果你的目的地是“向上”。那么你能够向左走,能够向右走,也能够向上走。可是不能够向下走);
3、 走过的格子马上塌陷无法再走第二次;
求走n步不同的方案数(2种走法仅仅要有一步不一样,即被觉得是不同的方案)。
Input
首先给出一个正整数C。表示有C组測试数据
接下来的C行。每行包括一个整数n (n<=20)。表示要走n步。
接下来的C行。每行包括一个整数n (n<=20)。表示要走n步。
Output
请编程输出走n步的不同方案总数;
每组的输出占一行。
每组的输出占一行。
Sample Input
2
1
2
Sample Output
3
7
解题思路:
要分两种情况来考虑。x(n)为向上,y(n)为向左跟向右,a(n)为当前方案数。
x(n) = x(n-1) + y(n-1);由于向上仅仅有一个方向。
y(n) = x(n-1) * 2 + y(n-1);
由于之前的向上能够走两个方向。而之前的向左或者向右仅仅能继续依照原来的方向走。由于走过的路会消失。
a(n) = x(n) + y(n);
所以能够推出: a(n) = a(n-1) * 2 + x(n-1) = a(n-1) * 2 + a(n-2);
代码例如以下:
#include<cstdio>
int a[30],t,n;
int main() {
a[0]=1;
for(int i=1; i<25; i++) {
for(int j=1; j<=i; j++) {
if(i-j-1>=0) a[i]+=2*a[i-j-1];
else a[i]+=2;
}
a[i]+=a[i-1];
}
scanf("%d",&t);
while(t--) {
scanf("%d",&n);
printf("%d\n",a[n]);
}
return 0;
}
最新文章
- I/O 函数总结
- webform 组合查询
- Spring中配置和读取多个Properties文件
- Toad快速入门
- C++ 提取字符串中的数字
- bzoj 2754 [SCOI2012]喵星球上的点名(后缀数组)
- 绘图quartz之阴影
- inux网卡与MAC地址绑定方法总结
- [ios2][转]iOS摇动检测 (UIAccelerometer)
- [DP之树形DP]
- Ecstore1.2启用mongodb添加索引
- vs 2015常用快捷键
- String.getBytes(),源码之下,了无秘密
- Kubernetes实战:目录
- springboot整合redis(注解形式)
- [Android] Android Studio 使用config.gradle统一管理项目的依赖库
- Ubuntu16.04安装JDK8与Tomcat7
- [tem]最长上升子序列
- C# 反射小结
- Selenium2(WebDriver)总结(五)---元素操作进阶(常用类)
热门文章
- vSphere VCSA5.5加入AD域环境问题记录
- HTML学习----------DAY2第四节
- HBase为什么快 HBase原理。 HBase几个问题
- 最简单的HTML5游戏——贪吃蛇
- 翻翻git之---炫酷的自己定义翻滚View TagCloudView
- WordPress改动新用户注冊邮件内容--自己定义插件
- UINavigationBar的系统渲染方式
- 三段式状态机 [CPLD/FPGA]
- POJ - 3847 Moving to Nuremberg 动归
- double和decimal的ToString(";#.##";)方法使用的是四舍五入;