NOIP 2008 普及组 传球游戏「建议收藏」

NOIP 2008 普及组 传球游戏「建议收藏」超时#include<bits/stdc++.h>usingnamespacestd;intn,m,ans;//第cnt次传球后,球在编号为x的同学手上voiddfs(intcnt,intx){ if(cnt==m){ if(x==0)ans++; return; } dfs(cnt+1,(x+1)%n); dfs(cnt+1,(x-1+n)%n); }intmain(){.

大家好,又见面了,我是你们的朋友全栈君。

  • 超时,满足40%的数据
#include <bits/stdc++.h>
using namespace std;

int n, m, ans;

//第cnt次传球后,球在编号为x的同学手上 
void dfs(int cnt, int x) { 
   
	if (cnt == m) { 
   
		if (x == 0) ans ++;
		return;
	}
	
	dfs(cnt + 1, (x + 1) % n);
	dfs(cnt + 1, (x - 1 + n) % n);	
}

int main() { 
   
	cin >> n >> m;	
	
	//第0次传球,球在编号为0的同学手上 
	dfs(0, 0);
	cout << ans;
	
	return 0;
}
  • 动态规划
#include <bits/stdc++.h>
using namespace std;

const int N = 40;
int n, m, dp[N][N];

int main() { 
   
	cin >> n >> m;

	//第0次传球在0号同学手中的方法数是1,即初始状态
	dp[0][0] = 1;
	
	//状态转移依赖于上一次传球的状态,所以外循环是1...m
	for (int i = 1; i <= m; i ++) { 
   
		for (int j = 0; j < n; j ++) { 
   
			//dp[i][j]表示第i次传球在j号同学手中的方法数
			dp[i][j] = dp[i - 1][(j + 1) % n] + dp[i - 1][(j - 1 + n) % n];
		}
	}
	cout << dp[m][0] << endl;

	return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/159232.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(2)


相关推荐

  • 虚函数表详解

    虚函数表详解本文转自:https://blog.csdn.net/lihao21/article/details/50688337关键词:虚函数,虚表,虚表指针,动态绑定,多态一、概述为了实现C++的多态,C++使用了一种动态绑定的技术。这个技术的核心是虚函数表(下文简称虚表)。本文介绍虚函数表是如何实现动态绑定的。二、类的虚表每个包含了虚函数的类都包含一个虚表。我们知道,当一个类(A)继承另一个类(B)时…

  • keil5如何生成bin文件_怎样创建一个文件夹

    keil5如何生成bin文件_怎样创建一个文件夹原因我碰到原因就是SCT加载文件的问题,我定义了不少段,所以导致bin文件变成了文件夹一般的Bin生成方法:在USER里面Run#1加上$K\ARM\ARMCC\bin\fromelf.exe–bin-o”$L@L.bin””#L”,生成错误出现文件夹,如果没有自定义SCT文件就可使用这种方法解决方法Keil里面的fromelf帮助,可以去看看bincombined_base与你自己的起始地址有关,$K\ARM\ARMCC\bin\fromelf.exe–bincombine

  • Redis主从复制原理_数据库主从复制的原理

    Redis主从复制原理_数据库主从复制的原理十八岁男孩爆肝Redis极品文章,必须三连奥里给爆赞

  • google Gmail_国外的新鲜玩意

    google Gmail_国外的新鲜玩意前不久,Google推出了Buzz,Buzz的说白了,就像QQ空间里面的好友关注,每天你登陆后,你都可以看到你所关注的好友做了哪些更新。让你和好友的关系更紧密。事实上,这个功能我甚至不会去使用它。为什么呢?因为我现在QQ上的好友更新已经太多了,我光是看QQ好友的更新已经觉得很累了。再去关注Buzz,想把我累死啊。。 所以其实现在中国的互联网市场上,成功还是腾讯和百度,Google是一个竞争…

    2022年10月15日
  • spring boot activiti工作流_activiti工作流优缺点

    spring boot activiti工作流_activiti工作流优缺点SpringBoot集成activiti工作流(模拟请假流程)链接:https://pan.baidu.com/s/10BT_Zertm1WBBrlrdE-QWQ提取码:zsq6学习视频地址见腾讯课堂:https://ke.qq.com/course/459167其他代码都是最原始的测试activiti的api代码,整合springboot的所有代码见下图.1.pom文件<dependency><groupId…

  • 队列数据结构的典型应用_kafka优先级队列

    队列数据结构的典型应用_kafka优先级队列上一篇文章讲解了队列的相关知识,同时用代码实现了一个队列结构。那么本文将介绍一下另一种特殊的队列结构,叫做优先级队列。上一篇文章的跳转链接——公众号:Lpyexplore的编程小屋关注我,每天更新,带你在python爬虫的过程中学习前端,还有更多电子书和面试题等你来拿数据结构——优先级队列一、什么是优先级队列一、什么是优先级队列在了解了什么是队列以后,我们再来了解优先级队列,顾名思义,优先级队列就是在队列的基础上给每个元素加上了先后顺序,我们仍然拿排队买票的例子来讲解。…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号