吹哨传球 （C++代码）

解题思路:





注意事项:





参考代码:老样子，代码军团开始进攻

1.史上噼里啪啦无敌简短代码
一道比较简单的dp题，我们仔细分析一下他的dp方程，F[i][j]表示在第i轮的时候第j个位置有几种方案传过来，因为传到这个位置可以从左边来也可以从右边来，所以到这个位置就可以有左右两种方案，传到这个位置的方案书就是左右的方案数之和，所以动归方程就是：
F[i][j]=F[i-1][j-1]+F[i-1][j+1]
但是还要注意边界，因为他自己本来就是有一种方案，所以边界就是在第0轮时他自己的位置值是1
而且还有在传到1或N的时候注意一下就好

#include<bits/stdc++.h>
#define maxn 100
using namespace std;int F[maxn][maxn];int main(){    int n,m;    scanf("%d%d",&n,&m);
    F[0][1]=1;//边界
    for(int i=1;i<=m;i++)//传m轮
      for(int j=1;j<=n;j++)//n个人
      {          int a=j-1,b=j+1;          if(j==1)a=n;//如果是1的话上一个就是N
          if(j==n)b=1;//如果是n的话下一个就是1
          F[i][j]=F[i-1][a]+F[i-1][b];
      }    printf("%d",F[m][1]);    return 0;
} 
 
2.本题的题意也比较好理解，转移公式也不难，
dp[i][j]中 i 表示传球的次数，j 表示被传球人的位置，
每一次转移后的值即是上一步该位置左右的人的值之和。AC~~~

#include<bits/stdc++.h>
#define For(i,j,k) 
for(register int i=j;i<=k;++i)
using namespace std;
int n,m,dp[105][105];
int main(){    
scanf("%d%d",&n,&m);
    dp[0][1]=1;   //初始化，第0次小蛮的值为 1
    For(i,1,m) For(j,1,n)
        dp[i][j]=dp[i-1][j==1?n:j-1]+dp[i-1][j==n?1:j+1]; //注意位置1左边是n，位置n右边是1
    printf("%d",dp[m][1]);  //输出第m次位置1 的答案
    return 0;
}

3.
这道dp题很有思维量，非常适合省选选手做（误）
其实就是上一次左右两边的可能数之和啦，判断一下环的起止
然后是边界条件，第0次，即没有开始前，球一定在1（小蛮）手中，赋值为1，其他为0

#include<bits/stdc++.h>
#define MAXN 9999999
using namespace std;int main()
{    int n,m,f[100][100];    scanf("%d%d",&n,&m);
    f[0][1]=1;    for(int i=2;i<=n;i++)
        f[0][i]=0;    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][n-1]+f[i-1][1];注意边界                else
                    f[i][j]=f[i-1][j+1]+f[i-1][j-1];//状态转移方程
            }    printf("%d",f[m][1]);    return 0;
}

4.
如果令f[i][j]表示经过ｉ次传球求在第ｊ个人手里，显然每个人只能从左边或者右边的人得到。
注意边界情况！！
蒟蒻代码当然要有。。。

#include<bits/stdc++.h>
using namespace std;
int f[50][50],n,m;
int main(){  scanf("%d%d",&n,&m);
  f[0][1]=1;  for (int i=2;i<=n;i++) f[0][i]=0;  for (int i=1;i<=m;i++)
  {      for (int j=1;j<=n;j++)
      {         if (j==1) f[i][j]=f[i-1][j+1]+f[i-1][n];         
else if (j==n) f[i][j]=f[i-1][j-1]+f[i-1][1];         else f[i][j]=f[i-1][j-1]+f[i-1][j+1];
      }
  }    
  printf("%d\n",f[m][1]);  return 0;
}