当前位置: 首页 > news >正文

计蒜客--蒜头君的新游戏

 1000ms
 131072K
工作空闲之余,蒜头君经常带着同事们做游戏,最近蒜头君发明了一个好玩的新游戏:n 位同事围成一个圈,同事 A 手里拿着一个兔妮妮的娃娃。蒜头君喊游戏开始,每位手里拿着娃娃的同事可以选择将娃娃传给左边或者右边的同学,当蒜头君喊游戏结束时,停止传娃娃。此时手里拿着娃娃的同事即是败者。

玩了几轮之后,蒜头君想到一个问题:有多少种不同的方法,使得从同事 A 开始传娃娃,传了 m 次之后又回到了同事 A 手里。两种方法,如果接娃娃的同事不同,或者接娃娃的顺序不同均视为不同的方法。例如 1−>2−>3−>1 和 1−>3−>2−>1 是两种不同的方法。

输入格式

输入一行,输入两个整数 n,m(3≤n≤30,1≤m≤30),表示一共有 n 位同事一起游戏,一共传 m 次娃娃。

输出格式

输出一行,输出一个整数,表示一共有多少种不同的传娃娃方法。

输出时每行末尾的多余空格,不影响答案正确性

要求使用「文件输入输出」的方式解题,输入文件为 game.in,输出文件为 game.out

样例输入

3 3

样例输出

2
 

知识点:DP

题解:

dp[i][j ]数组表示的是  从A同事开始传娃娃,经过m次传递之后 依旧到达A同事手中的方法数目

初始化  dp[0][1]=1表示没走一步  娃娃刚开始就在1  号同事手中了此时 方法数为1

或者一开始的时候就在1号同事手中    那么dp[1][2]=1,dp[1][n]=1;

只有在 一号位置   走一步 到达 2或者n号位置的方法数为1;

#include<iostream>
using namespace std;
int n, m;
int dp[100][100];
int main() {cin >> n >> m;//假设刚开始的时候 娃娃在 1 的手里//dp[0][1] = 1;dp[1][2] = 1;dp[1][n] = 1;for (int i = 2; i <= m; i++) {//i表示传递了多少次,j表示哪个人传递for (int j = 1; j <= n; j++) {if (j == 1) {dp[i][j] = dp[i - 1][2] + dp[i - 1][n];//cout << dp[i][j] << endl;}else if (j == n) {dp[i][j] = dp[i - 1][1] + dp[i - 1][n - 1];}else {dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];//cout << dp[i][j] << endl;}}}cout << dp[m][1] << endl;return 0;}

 


http://www.taodudu.cc/news/show-6102240.html

相关文章:

  • 原生小程序转Taro开发
  • 手把手系列之三十——手把手教你做番薯小煎饼
  • 夏彭年老夫子论孔子
  • 【C++进阶知识】C++类的继承和派生
  • 小红书怎么涨粉最快?小红书涨粉最快的方法分享
  • 头条搬砖最新实操玩法
  • 微信小程序如何进行反编译详细教程
  • 红颜弹指老,刹那芳华(转载 作者:程灵素)
  • 刘邦六大用人之道,很值得管理人员学习
  • 冰山下面的刘邦
  • 以铜为镜,正衣冠,以史为镜,明心志,以人为镜,明得失
  • 从平民到帝皇——给企业主的启示
  • 【GDAL基础教程】多张二维tif数据转三维tif数据
  • Unity旋转基础——二维旋转与三维旋转
  • 关于服务器登录用户信息查看的若干命令
  • 索尼天气 v1.0.2 魅族定制版,纯净无广告的天气预报应用
  • 最简单的Go Dockerfile编写姿势
  • 运行环信Android Demo常见问题以及语音消息播放声音小的解决方法
  • win10安装并配置node.js
  • Springboot文件上传报错:failed to convert java.lang.String to org.springframework.util.unit.DataSize
  • 腾讯云8核 16G 18M配置服务器评测
  • 腾讯云轻量8核16G18M服务器带宽CPU流量性能测评
  • 8 年 Java 开发含泪刷题,架构岗现在好难进,有点崩溃
  • 腾讯云服务器8核16G18M配置测评
  • 成功将TTF字体从18M裁剪到1.8M
  • 腾讯云:轻量服务器8核16G18M配置性能及限制条件说明
  • 腾讯云轻量服务器性能评测:配置 8核 16G 18M 带宽
  • 腾讯云服务器性能评测:8核 16G 18M 配置
  • 腾讯云8核16G18M轻量服务器CPU带宽流量性能测评
  • 腾讯云轻量8核16G服务器18M带宽CPU流量性能测评