蒜头君的新游戏
2023-02-18 16:34:54 时间
问题描述工作空闲之余,蒜头君经常带着同事们做游戏,最近蒜头君发明了一个好玩的新游戏:n 位同事围成一个圈,同事 A 手里拿着一个兔妮妮的娃娃。蒜头君喊游戏开始,每位手里拿着娃娃的同事可以选择将娃娃传给左边或者右边的同学,当蒜头君喊游戏结束时,停止传娃娃。此时手里拿着娃娃的同事即是败者。
玩了几轮之后,蒜头君想到一个问题:有多少种不同的方法,使得从同事 A 开始传娃娃,传了 m 次之后又回到了同事 A 手里。两种方法,如果接娃娃的同事不同,或者接娃娃的顺序不同均视为不同的方法。例如1−>2−>3−>1 和 1->3->2->1 是两种不同的方法。
输入格式
输入一行,输入两个整数n,m(3≤n≤30,1≤m≤30),表示一共有 n 位同事一起游戏,一共传 m 次娃娃。
输出格式
输出一行,输出一个整数,表示一共有多少种不同的传娃娃方法。
样例输入
3 3
样例输出
2
思路:
首先是拆分过程, 定义子状态:
从 A 开始传, 第 m 次传到 A , 那么只能从 A 的左边和右边传过去.
现在定义状态 dp[m, 0] 为传了 m 次传到 A 的方法数,
状态转移方程为 dp[m, 0] = dp[m - 1, 1] + dp[m - 1, (0 - 1) % n]
dp[m - 1, 1] 表示 传了 m - 1 次, 传到 1 的方法数
dp[m - 1, (0 - 1) % n] 表示 传了 m - 1 次, 传到 (0 - 1) % n的方法数
取余的目的是将这些人围成一个环
代码:
AC代码(正推法)
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
int n, m, dp[35][35];
memset(dp, 0, sizeof(dp));
cin >> n >> m;
dp [1][0] = dp[0][1] = dp[0][n + 1] = 1;
for(int i = 1; i <= m; ++i){
for(int pos = 1; pos <= n; ++pos){
dp[i][pos] = dp[i - 1][pos - 1] + dp[i - 1][pos + 1];
}
dp[i][n + 1] = dp[i][1];
dp[i][0] = dp[i][n];
}
cout << dp[m][1] << endl;
return 0;
}
正推法2:
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n, m;
long long dp[50][50];
int main()
{
memset(dp,0,sizeof(dp));
cin >> n >> m;
dp[1][2]=1;
dp[1][n]=1;
for(int i=2;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
int tmp1 = j - 1;
if (tmp1 == 0)tmp1 = n;
int tmp2 = (j+1)%n;
if (tmp2 == 0)tmp2 = n;
dp[i][j]=dp[i-1][tmp1]+dp[i-1][tmp2];
}
}
cout << dp[m][1];
return 0;
}
TLE代码(逆推法)
#include <iostream>
#include <cstdio>
using namespace std;
int n, m;
long long f(int cs, int r)
{
if (cs == 1 && r == 2)return 1;
if (cs == 1 && r == n)return 1;
if (cs==1)return 0;
int tmp1 = r - 1;
if (tmp1 == 0)tmp1 = n;
int tmp2 = (r+1)%n;
if (tmp2 == 0)tmp2 = n;
return f(cs - 1, tmp1)+f(cs-1,tmp2);
}
int main()
{
cin >> n >> m;
long long ans=f(m,1);
cout << ans;
}
相关文章
- 如何让Redis兼顾效率、成本和运维?看vivo优化出妙招
- 微服务-技术专区-链路追踪(pinpoint)-部署使用
- 梳理总结-备份整理-知识点问题梳理
- MySQL-技术专区-mysql数据库权限管理
- MySQL-技术专区-数据库权限管理
- 开源软件的盈利模式
- 分布式-技术专区-Redis分布式锁实现-第二步
- Groovy系列(5)- Groovy IO操作
- 分布式-技术专区-Redis分布式锁实现-第一步
- JPA接口整理归纳方法规则
- 备份整理-实用归纳
- Groovy系列(4)- Groovy集合操作
- Groovy系列(3)- Groovy基础语法
- Zookeeper-技术专区-运作流程分析介绍
- 技术哲学-技术定位和思想
- Groovy系列(1)- Groovy简述
- Jmeter系列(30)- 性能指标(3) | 性能指标峰值
- Jmeter系列(29)- 性能指标(2) | 并发数
- 分布式-技术专区-Redis并发竞争key的解决方案详解
- Jmeter系列(28)- 性能指标(1) | 常见性能指标