d105 - NOIP 2008 3.传球游戏

🔗 前往 ZeroJudge 原題

題目描述

題目描述了一個傳球遊戲，n 個同學排成一個圓圈，球從某人開始傳 m 次後回到原點。要求計算有多少種不同的傳球方法。

解題思路

本題可以使用動態規劃 (DP) 解決。dp[i][j] 表示傳了 i 次球後，第 j 個人持有球的方案數。由於題目要求球最終回到小蠻 (編號為 0) 手中，因此最終答案是 dp[b][0]。

初始化 dp[0][0] = 1，表示傳 0 次球時，小蠻持有球的方案數為 1。

然後，對於每次傳球，我們考慮從第 j 個人傳球到左右兩個人。如果 j 是 0 (小蠻)，則可以傳給 n-1 和 1。如果 j 是 n-1，則可以傳給 0 和 n-2。否則，可以傳給 j+1 和 j-1。

因此，狀態轉移方程如下：

• dp[i+1][j+1] += dp[i][j] (傳給右邊)
• dp[i+1][j-1] += dp[i][j] (傳給左邊)

需要注意邊界情況，例如當 j 為 0 或 n-1 時，傳球的目標位置需要進行調整。

複雜度分析

• 時間複雜度: O(n*m)
• 空間複雜度: O(n*m)

程式碼

#include <iostream>
using namespace std;
long long int dp[35][35];
int main(){
	long long int a,b;
	cin >> a >> b;
	dp[0][0]=1;
	for(int y=0;y<b;++y){
		for(int x=0;x<a;++x){
			if(dp[y][x]!=0){
				if(x==0){
					dp[y+1][a-1]+=dp[y][x];
					dp[y+1][1]+=dp[y][x];
				}
				else if(x==a-1){
					dp[y+1][0]+=dp[y][x];
					dp[y+1][a-2]+=dp[y][x];
				}
				else{
					dp[y+1][x+1]+=dp[y][x];
					dp[y+1][x-1]+=dp[y][x];
				}
			}
		}
	}
	cout << dp[b][0];
}