题解 P1057 【传球游戏】

小学奥数中的传球法解题~~~

首先来讲一下思路：这种题最适合画树形图，类似于一棵二叉树；

但是貌似画不完那么大一棵树！！！

So，我们想到了列表（其实是老师讲的）

或者叫DP

表中，a[ i ][ j ]表示第i次传球传到编号为j的仁兄的方法数，而a[ i ][ j ]则是由a[ j-1 ][ i-1 ]和a[ j+1 ][ i-1 ]传递来的（注意边缘情况）。

DP转移方程就是：

(a_{j,i}=a_{j-1,i-1}+a_{j+1,i-1})

特地的，

当(j=1)的时候，(a_{1,i}=a_{n,i-1}+a_{2,i-1})

而当(j=n)时，(a_{n,i}=a_{1,i-1}+a_{n-1,i-1})

上代码！

#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n,m;
  cin>>n>>m;
  int a[n+1][m+1];
  memset(a,0,sizeof(a));
  a[1][0]=1;
  for(int i=1;i<=m;i++)
  {
    a[1][i]=a[n][i-1]+a[2][i-1];
    for(int j=2;j<n;j++) 
        a[j][i]=a[j-1][i-1]+a[j+1][i-1];
    a[n][i]=a[1][i-1]+a[n-1][i-1];
  }
  cout<<a[1][m];
  return 0;
}

---

2020/2/6 初一的宋长纬已修改