P1057传球游戏

SkylarHoffenberg · 2021-02-03 20:43:34 · 个人记录

题目大意：n名同学，m次传球（可传左、右两边），问有多少中可能还会到1号同学手里（从1号开始传）

正解（？）：dp

其实数据很小干脆打表应该（？）也能过？

思路：假设n个人：小蛮的选择：2或n，给2:3或1

=>两种选择的loop（原理：球传到他手上的路径数是球传到他左边同学的路径数与球传到他右边同学的路径数之和）：f[i][j]=f[i-1][j-1]+f[i-1][j+1]

好像有些不对？？

=>边界处理：小蛮&最后的同学

然后就有了以下的代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn=35;
int n,m,f[maxn][maxn];

int main(){
    cin>>n>>m;
    f[0][1]=1;//一定要初始化！！qwq输出0吃了个大惊 
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            if(j==1)f[i][j]=f[i-1][n]+f[i-1][2];
            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]<<endl;
    return 0;
}