洛谷【P1057】传球游戏
2024-09-01 12:01:57
https://www.luogu.org/problemnew/show/P1057
题目描述
在体育课上, 老师带着同学们一起做传球游戏. 游戏规则是这样的: n 个同学站成一个圆圈, 其中的一个同学手里拿着一个球. 当老师吹哨子时同学们开始传球, 每个同学可以把球传给自己左右两个同学中的一个. 当老师再次吹哨子时, 传球停止, 这时拿着球的同学就要给大家表演一个节目.
聪明的小蛮同学提出了一个问题: 有多少种不同的传球方法使得从小蛮手中开始传的球在传了 m 次之后又回到小蛮手中呢?
输入输出格式
输入格式:
一行, 有两个空格隔开的整数 n, m ( 3 ≤ n ≤ 30, 1 ≤ m ≤ 30 ).
输出格式:
一个整数, 表示符合题意的方法数.
输入输出样例
输入样例:
3 3
输出样例:
2
解题思路
状态转移方程
设 f[i][j] 为第 j 次传球传给第 i 名同学的方法数, 有 f[i][j] = f[i - 1][j - 1] + f[i + 1][j - 1].
实现
#include <iostream> #include <cstdio> using namespace std; int n, m; ][]; int main() { scanf("%d%d", &n, &m); dp[][] = ; ; i <= m; ++i) { dp[][i] = dp[n][i - ] + dp[][i - ]; ; j < n; ++j) dp[j][i] = dp[j - ][i - ] + dp[j + ][i - ]; dp[n][i] = dp[n - ][i - ] + dp[][i - ]; } printf(][m]); ; }
最新文章
- google play iap 常见问题
- c++容器
- (转)SVN分支/合并原理及最佳实践
- ios之AFN上传下载详细步骤(2)
- [iOS]SourceTree+oschina实现代码远程托管
- Arduino报错
- 怎么在 html 中 动态的加载一个 script
- git 与 github 最简单的用法
- C语言文件操作解析(五)之EOF解析(转载)
- POJ 3280 间隔DP
- C++随机数rand(), srand()
- Java多线程(二) —— 线程安全、线程同步、线程间通信(含面试题集)
- weblogic AND jboss 反序列化漏洞
- listview 点击时间被拦截
- Asp.net与office web apps的整合
- Python2.7-collections
- MySQL常用处理方法
- springmvc后台生成验证码
- Java里的堆(heap)栈(stack)和方法区(method)
- vs启动项目提示Web 服务器被配置为不列出此目录的内容。
热门文章
- Java 常用IO流操作详解
- Java 8-Stream流
- java二维码工具类,中间带LOGO的,很强大
- 轻量ORM-SqlRepoEx (十六)最佳实践之Dapper(2)
- activiti获取流程图中的所有信息包括变量名
- MySQL常用:Got a packet bigger than &#39;max_allowed_packet&#39; bytes &; MySQL开远程服务
- js清除浏览器缓存
- Spark SQL join的三种实现方式
- (数据科学学习手札53)Python中tqdm模块的用法
- Enable CSS active pseudo styles in Mobile Safari