专栏首页开心的学习之路算法训练 传球游戏

算法训练 传球游戏

问题描述

  上体育课的时候,小蛮的老师经常带着同学们一起做游戏。这次,老师带着同学们一起做传球游戏。   游戏规则是这样的:n个同学站成一个圆圈,其中的一个同学手里拿着一个球,当老师吹哨子时开始传球,每个同学可以把球传给自己左右的两个同学中的一个(左右任意),当老师再次吹哨子时,传球停止,此时,拿着球没传出去的那个同学就是败者,要给大家表演一个节目。   聪明的小蛮提出一个有趣的问题:有多少种不同的传球方法可以使得从小蛮手里开始传的球,传了m次以后,又回到小蛮手里。两种传球的方法被视作不同的方法,当且仅当这两种方法中,接到球的同学按接球顺序组成的序列是不同的。比如有3个同学1号、2号、3号,并假设小蛮为1号,球传了3次回到小蛮手里的方式有1->2->3->1和1->3->2->1,共2种。

输入格式

  共一行,有两个用空格隔开的整数n,m(3<=n<=30,1<=m<=30)。

输出格式

  t共一行,有一个整数,表示符合题意的方法数。

样例输入

3 3

样例输出

2

数据规模和约定

  40%的数据满足:3<=n<=30,1<=m<=20   100%的数据满足:3<=n<=30,1<=m<=30 思路 动态规划题,用数组dp[i][j]来存储第i次传到第j个人的可能性。假设小蛮的编号为0,输出就是第m次传到0号的可能性。dp数组的每一个数的填写就是该列前一行的左右两数和。

#include <cstdio>
#include <cstring>

int dp[35][35];

int main()
{
	int m, n;
	int i, j;
	scanf("%d%d", &n, &m);
	memset(dp, 0,  sizeof(dp));
	dp[1][1] = dp[1][n - 1] = 1;
	for(i = 2; i <= m; i++)
	{
		for(j = 0; j < n; j++)
		{
			dp[i][j] = dp[i - 1][(j + 1) % n];
			if(j - 1 < 0)
				dp[i][j] += dp[i - 1][n - 1];
			else
				dp[i][j] += dp[i - 1][j - 1];
		}
	}
	printf("%d\n", dp[m][0]);
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 用神经网络玩史莱姆排球

    利用递归神经网络玩的"史莱姆排球"游戏。你能打败AI吗?

    Shawn_Kid
  • 腾讯AI足球队夺冠Kaggle竞赛,绝悟强化学习方案迁移至足球队

    12月30日,腾讯宣布其人工智能球队摘得首届谷歌足球Kaggle竞赛冠军。该冠军球队来自腾讯AI Lab研发的绝悟WeKick版本,凭借1785.8的总分在与全...

    AI科技大本营
  • 神经网络小游戏——泥煤排球

    我记得在当年Java小程序仍然很受欢迎的时候有个游戏叫“软泥小排球”。虽然这个游戏在物理上面有一些投机取巧的部分,但是许多跟我一样的孩子却被它深深的吸引了,并且...

    庹阳
  • 腾讯AI Lab绝悟团队夺冠Kaggle足球AI竞赛

    Google Research 与英超曼城俱乐部在 Kaggle 平台上联合举办的 11v11 足球 AI 竞赛 Google Football 近日宣布最终结...

    CV君
  • 用深度Q网络玩电子游戏

    蛮挫败的,所以我决定建立一个深度Q网络,用这个网络学习如何在任一电子游戏中打败我的妹妹。

    AI研习社
  • 每秒处理240万帧游戏画面,AI训练成本降低80%,谷歌开源RL并行计算框架

    AI训练中的并行计算就是如此,纵使你有一千张GPU,也无法实现单机训练一千倍的效果。

    量子位
  • 【游戏】国外大神建立了一个深度神经网络来玩足球游戏FIFA 18

    游戏中的人工智能机器人通常是通过手动编码来构建一系列游戏智能的规则。在很大程度上,这种方法在使机器人模仿人类行为方面做得更好。然而,对于大多数游戏来说,究竟是机...

    AiTechYun
  • GAN 作者 Ian Goodfellow 最新论文:对神经网络策略的对抗性攻击

    【新智元导读】迄今为止,多数对于对抗样本的研究是关于对抗样本对监督式学习算法影响的。一个最新的技术报告研究了对抗性攻击干扰代理训练,使其无法学到任何有意义的事情...

    新智元
  • 备战世界杯!先用深度学习与强化学习踢场 FIFA 18

    构建能玩 FIFA 游戏的智能体与游戏内置的 Bot 是不一样的,它不能访问任何内部程序信息,只能与人一样获得屏幕的输出信息。游戏窗口截图就是所有需要馈送到智能...

    机器之心
  • Google Research Football (scenario 11) 实验

    在之前的公众号文章中我们介绍了Football Academy中的两个scenario的实验:

    用户1908973
  • IJCAI 2019 | 有趣!这是一篇玩倩女幽魂的多智能体强化学习研究

    混合动作空间:与离散动作空间或连续动作空间不同,拥有混合动作空间的智能体在每一步执行动作时都需要选择一个离散动作以及该离散动作对应的一个或多个连续性动作参数的值...

    机器之心
  • 游戏与人工智能

    在人工智能的发展上的道路上,游戏到底扮演着一个怎样的角色?也许接下来五分钟的阅读(多图预警),会让你得到一个较为清晰的答案。

    leland
  • 下个目标是攻克FIFA游戏?DeepMind让AI自学传球配合

    今天,这家英国的AI公司开源了机器人足球模拟环境MuJoCo Soccer,实现了对2v2足球赛的模拟。

    量子位
  • 你在网上看到的0失误游戏视频,可以是用AI生成的丨Demo在线可玩

    只需要敲几下键盘,就能控制视频中某个目标的方法,叫做“可玩视频生成器” (playable video generation)。

    量子位
  • 利用深度神经网络创建一个球星的脸 效果堪比真人!

    AiTechYun 编辑:Yining 游戏工作室花费数百万美元和数千个开发小时来设计游戏图案,试图让它们看起来尽可能接近现实。虽然在过去的几年里,游戏图案看起...

    AiTechYun
  • DeepMind 发布新架构:让AI 边玩游戏边强化学习

    本文出自:雷锋网(leiphone-sz) 论文标题:IMPALA: Scalable Distributed Deep-RL with Importance ...

    刀刀老高
  • Meet CreateAMind Cuju ( 谷歌足球 SOTA )

    谷歌足球(Google Research Football)是Google Brain 开发的一个足球仿真策略游戏。

    用户1908973
  • 备战世界杯!先用深度学习与强化学习踢场 FIFA 18

    构建能玩 FIFA 游戏的智能体与游戏内置的 Bot 是不一样的,它不能访问任何内部程序信息,只能与人一样获得屏幕的输出信息。游戏窗口截图就是所有需要馈送到智能...

    IT派
  • 视频 | DeepMind发布新架构,让AI边玩游戏边强化学习

    AI 科技评论按:这里是,雷锋字幕组编译的 Two minutes paper 专栏,每周带大家用碎片时间阅览前沿技术,了解 AI 领域的最新研究成果。

    AI科技评论

扫码关注云+社区

领取腾讯云代金券