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)


相关推荐

发表回复

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

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