1 solutions

  • 0
    @ 1 year ago

    动态规划(OnmOnm)

    状态表示f[i][j]f[i][j]表示第ii轮的时候球在第jj个人 的方案数,f[i][j]=f[i1][j1]+f[i1][j+1]f[i][j]=f[i-1][j-1]+f[i-1][j+1]需要注意边界。

    #include<bits/stdc++.h>
    using namespace std;
    const int N=33;
    int f[N][N]; //f[i][j]表示第i次传球的时候,球在第j个人的方案数
    int n,m;
    int main()
    {
    	cin>>n>>m;
    	f[0][0]=1; //起点
    	for(int i=1;i<=m;i++) //枚举轮
    	{ 
    		for(int j=0;j<n;j++) //枚举每个人
    		{
    			f[i][j]=f[i-1][(j+1)%n]+f[i-1][(j+n-1)%n];
    			//     当j==n-1时(j+1)%n==0 同理当j==0,时(j+n-1)%n=n-1,处理相邻
    		}
    	}
    	cout<<f[m][0]<<endl; //传了m次,最后球在0号点
    	return 0;
    }
    
    • 1

    Information

    ID
    423
    Time
    1000ms
    Memory
    128MiB
    Difficulty
    10
    Tags
    # Submissions
    9
    Accepted
    3
    Uploaded By