[NOIP2008]传球游戏

题意：

n个同学围成一个圆圈进行传球游戏，一个同学传球时只能传给左右的同学，传m次最终回到第一个人手里，问你有多少种情况？

我们可以发现，任何一个位置都只能从左边和右边传过来，那么他只能从他左边和他右边的同学手上接到球

思路

我们再整理一下原问题：从1开始传球，第m步回到1号的情况数

得出子问题：子问题：从1开始传球第i步到达j号的情况数

我的解法：DP

$f_{i,j}$ 表示第i次传球后在j位置的情况数

得到状态转移方程：

如果 $j$ == $n$ ： $f_{i,j}=f_{i-1,1}$ + $f_{i-1,n-1}$

如果 $j$ ==1 ： $f_{i,j}=f_{i-1,n}$ + $f_{i-1,2}$

如果 $j$ < $n$ 并且 $j$ >1： $f_{i,j}=f_{i-1,j-1}$ + $f_{i-1,j}$ + ${_1}$

答案就是 $f_{m,1}$

表格：

alt

CODE:

#include<bits/stdc++.h>
#define oo INT_MAX
#define int long long
using namespace std;
int n,m,f[35][35];
signed main() {
	cin>>n>>m;
	f[0][1]=1;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			if(j==1) f[i][j]=f[i-1][2]+f[i-1][n];
			else if(j==n) f[i][j]=f[i-1][1]+f[i-1][n-1];
			else f[i][j]=f[i-1][j-1]+f[i-1][j+1];
		}
	}
	cout<<f[m][1];
}