NOIP 2008 传球游戏
2024-09-03 06:25:09
洛谷 P1057 传球游戏
JDOJ 1536: [NOIP2008]传球游戏 T3
Description
上体育课的时候,小蛮的老师经常带着同学们一起做游戏。这次,老师带着同学们一起做传球游戏。
游戏规则是这样的:n个同学站成一个圆圈,其中的一个同学手里拿着一个球,当老师吹哨子时开始传球,每个同学可以把球传给自己左右的两个同学中的一个(左右任意),当老师再次吹哨子时,传球停止,此时,拿着球没传出去的那个同学就是败者,要给大家表演一个节目。
聪明的小蛮提出了一个有趣的问题:有多少种不同的传球方法可以使得从小蛮手里开始传的球,传了m次以后,又回到小蛮手里。两种传球方法被视作不同的方法,当且仅当这两种方法中,接到球的同学按接球顺序组成的序列是不同的。比如有三个同学1号、2号、3号,并假设小蛮为1号,球传了三次回到小蛮手里的方式有1-> 2-> 3-> 1和1-> 3-> 2-> 1,共2种。
Input
输入共一行,有两个用空格隔开的整数n,m(3< =n< =30,1< =m< =30)。
Output
输出共一行,有一个整数,标示符合题意的方法数。
Sample Input
3 3
Sample Output
2
HINT
40%的数据满足:3< =n< =30 1< =m< =20
100%的数据满足:3< =n< =30 1< =m< =30
Source
题解:
递推。
我觉得动归的题解只需要4个部分:
1、状态:设置\(dp[i][j]\)表示经过\(j\)次传球回到\(i\)号的方案数。
2、初值:\(dp[1][0]=1\)。可以结合上述状态理解。
3、转移:\(dp[i][j]=dp[i-1][j-1]+dp[i+1][j-1]\).为了处理环状结构,我们需要特殊处理\(i=1\)以及\(i=n\)的情况。
4、答案:\(dp[1][m]\).
代码:
#include<cstdio>
using namespace std;
int n,m;
int dp[31][31];//dp[i][j]表示经过j次传球传回i号人的方案数
int main()
{
scanf("%d%d",&n,&m);
dp[1][0]=1;
for(int i=1;i<=m;i++)
{
dp[1][i]=dp[n][i-1]+dp[2][i-1];
for(int j=2;j<n;j++)
dp[j][i]=dp[j-1][i-1]+dp[j+1][i-1];
dp[n][i]=dp[n-1][i-1]+dp[1][i-1];
}
printf("%d",dp[1][m]);
return 0;
}
最新文章
- 前端自动化测试 —— TDD环境配置(React+TypeScript)
- 冰冻三尺非一日之寒--web框架Django(三)
- UOJ149 【NOIP2015】子串
- Effective Objective-C 2.0 — 第二条:类的头文件中尽量少引入其他头文件
- Consul Template的简单使用
- FormCreate &; FormActivate &; FormShow执行顺序演示
- Liunx更新源
- LINQ(LINQ to Entities)
- Robotium---环境搭建及入门示例
- VBoxManage命令详解
- 手游架构-REST架构
- canvas认识
- python学习(2)
- GeoHash核心解析
- NOIP 2000 提高组 题解
- 两种利用GCD实现分步获取结果的方式和SDWebImage缓存机制的验证
- lambda+mutable配合move实现单函数多程序域
- UOJ#206. 【APIO2016】Gap 构造 交互题
- Android 全局弹出版本更新 Dialog 思考和解决办法
- MetaMask/provider-engine-2-代码