首页 > 其他 > 详细

洛谷【P1057】传球游戏

时间:2019-01-13 01:34:47      阅读:131      评论:0      收藏:0      [点我收藏+]

标签:bsp   输出   col   转移   一起   ()   href   ble   https   

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 ].

实现

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 
 5 int n, m;
 6 int dp[31][31];
 7 
 8 
 9 int main()
10 {
11     scanf("%d%d", &n, &m);
12     dp[1][0] = 1;
13     for (int i = 1; i <= m; ++i) {
14         dp[1][i] = dp[n][i - 1] + dp[2][i - 1];
15         for (int j = 2; j < n; ++j)
16             dp[j][i] = dp[j - 1][i - 1] + dp[j + 1][i - 1];
17         dp[n][i] = dp[n - 1][i - 1] + dp[1][i - 1];
18     }
19     printf("%d\n", dp[1][m]);
20     return 0;
21 }

 

洛谷【P1057】传球游戏

标签:bsp   输出   col   转移   一起   ()   href   ble   https   

原文:https://www.cnblogs.com/justlikeoldtimes/p/10261562.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号