目錄

題目

工作空閑之余，蒜頭君經(jīng)常帶著同事們做游戲，最近蒜頭君發(fā)明了一個好玩的新游戲：n位同事圍成一個圈，同事 A 手里拿著一個兔妮妮的娃娃。蒜頭君喊游戲開始，每位手里拿著娃娃的同事可以選擇將娃娃傳給左邊或者右邊的同學(xué)，當(dāng)蒜頭君喊游戲結(jié)束時，停止傳娃娃。此時手里拿著娃娃的同事即是敗者。

玩了幾輪之后，蒜頭君想到一個問題：有多少種不同的方法，使得從同事 A 開始傳娃娃，傳了m次之后又回到了同事 A 手里。兩種方法，如果接娃娃的同事不同，或者接娃娃的順序不同均視為不同的方法。例如1?>2?>3?>1和1?>3?>2?>1是兩種不同的方法。

輸入格式

輸入一行，輸入兩個整數(shù)n,m(3≤n≤30,1≤m≤30)，表示一共有n位同事一起游戲，一共傳m次娃娃。

輸出格式

輸出一行，輸出一個整數(shù)，表示一共有多少種不同的傳娃娃方法。

輸出時每行末尾的多余空格，不影響答案正確性

要求使用「文件輸入輸出」的方式解題，輸入文件為game.in，輸出文件為game.out

樣例輸入

3 3

樣例輸出

題解：

知識點(diǎn)：DP

分析：我們首先用dp[i][j]表示第i次傳到第j個人的總次數(shù)，然后得出dp狀態(tài)轉(zhuǎn)移方程：dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1];，第i次傳到j(luò)這個人的次數(shù)=第i-1次傳到j(luò)-1這個人和j+1這個人，注意第0次傳到第一個人的次數(shù)為1，要預(yù)判的，dp中還有特殊情況：1這個人和n這個人的次數(shù)計(jì)算，畢竟題意中這是一個環(huán)，但數(shù)組是線性的。

代碼：

#include
#include
using namespace std;
const int NOIP=50;//祝考NOIP的人一切順利（例如我）
int dp[NOIP][NOIP];//dp[i][j]表示第i次傳到第j個人的總次數(shù)
int main(){
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout); 
	int n,m;
	cin>>n>>m;
	dp[0][1]=1;//預(yù)處理
	for (int i=1;i<=m;i++){
		for (int j=1;j<=n;j++){
			if (j==1){//特判當(dāng)傳到第1個人時
				dp[i][j]=dp[i-1][n]+dp[i-1][j+1];
				continue;
			}
			if (j==n){//特判當(dāng)傳到第n個人時
				dp[i][j]=dp[i-1][1]+dp[i-1][j-1];
				continue;
			}
			dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1];//從兩方的人傳到此人手里
		}
	}
	cout<