poj 4982 踩方格
2024-10-16 16:49:17
4982:踩方格
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
-
有一个方格矩阵,矩阵边界在无穷远处。我们做如下假设:
a. 每走一步时,只能从当前方格移动一格,走到某个相邻的方格上;
b. 走过的格子立即塌陷无法再走第二次;
c. 只能向北、东、西三个方向走;
请问:如果允许在方格矩阵上走n步,共有多少种不同的方案。2种走法只要有一步不一样,即被认为是不同的方案。 - 输入
- 允许在方格上行走的步数n(n <= 20)
- 输出
- 计算出的方案数量
- 样例输入
-
2
- 样例输出
-
7 题解
l[i]表示最后一步向左走到达第i个格,那么它上一格不能是从右边走得到,
r[i]表示最后一步向右走到达第i个格,那么它上一格不能是从左边走得到,
u[i]表示最后一步先上走到达第i个格;#include<iostream>
#include<cstdio>
using namespace std;
int n,ans;
int l[30],r[30],u[30];
int main()
{
cin>>n;
if (n==1) cout<<3;
else
{
l[1]=1;
r[1]=1;
u[1]=1;
for (int i=2;i<=n;i++)
{
l[i]=l[i-1]+u[i-1];
r[i]=r[i-1]+u[i-1];
u[i]=l[i-1]+r[i-1]+u[i-1];
}
ans=l[n]+r[n]+u[n];
cout<<ans<<endl;
}
return 0;
}
最新文章
- Java–cvc-complex-type.4:Attribut ‘version’ must appear on element ‘web-app’
- Javascript中call,apply,bind方法的详解与总结
- TortoiseSVN status cache占用CPU高
- 受限玻尔兹曼机(RBM)学习笔记(二)网络结构
- Sharepoint学习笔记—习题系列--70-573习题解析 --索引目录
- Java基础之一组有用的类——为标记定义自己的模式(ScanString)
- JAVA中在Myeclipse里把表导入成相应的poco实体类
- visibility和display的区别
- Cygwin下软件安装 - apt-cyg
- QT核心编程之调试技术 (g)
- sql 查询练习
- mysql的过程和Oracle的区别
- PHP多维数组元素操作类
- EmbossMaskFilter BlurMaskFilter 学习
- 拔高课程_day14_课堂笔记
- 如何写一个SSH项目(三)如何进行交互的
- 图的最小环floyed
- Linux常用命令之帮助和用户管理命令
- 异步请求 ajax的使用详解
- Git 分支合并:合并某次提交
热门文章
- poj2318 水题(二分+叉积)
- 优化exp/imp导入导出速度大全
- 服务器CPU使用率高的原因分析与解决办法
- Android eclipse下数据开源框架GreenDao的配置
- xcode设置项目图标玻璃镜效果
- media screen 响应式布局(知识点)
- 黑马程序猿_try-catch-finally
- [yueqian_scut]蓝牙防丢器原理、实现与Android BLE接口编程
- spring mvc DispatcherServlet详解前传---HttpServletBean类
- codevs 2495 水叮当的舞步IDA*