题解 | #[NOIP2008]传球游戏#

上面的题解讲的很详细了，我补充几句，dp[i][j]表示第j次选第i人的方法数，根据题意，每一个人可以从他左边的人与右边的人拿到球，因此要将第一个人左边与右边的人初始化为1，不过由次要注意第一个人不可能自己传给自己，因此要特判，详情见代码；

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=35;

int n,m;
int dp[N][N];

inline int read()
{
    int x=0,t=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')t=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    
    return x*t;
}
int main()
{
    n=read(),m=read();
    //回忆dp数组的含义，传0次代表从起点开始
    //传一次只能由起点往左右传，因此只用初始化起点左右两边的人即可
    dp[1][1]=dp[n-1][1]=1;
    
    for(int j=2;j<=m;j++)//先按传的次数遍历，上边传一次已经初始化过了，2开始
        for(int i=0;i<n;i++)
        {
        	//特判条件，自己不能传给自己
            if((i-1+n)%n==0&&j==2)dp[i][j]=dp[(i+1+n)%n][j-1];
            else if((i+1+n)%n==0&&j==2)dp[i][j]=dp[(i-1+n)%n][j-1];
            else dp[i][j]=dp[(i-1+n)%n][j-1]+dp[(i+1+n)%n][j-1];
        }
    
    cout<<dp[0][m]<<endl;
}