NOIP 2008 普及组 复赛 ball 传球游戏
NOIP 2008 普及组 复赛 ball 传球游戏
//p1057 传球游戏 //该题与 P1164 小A点菜 有点 象 //模拟样例，一直觉得挺奇怪的，应该有很多种啊，一模拟，发现1->2->1是不行的。 //样例弄懂的，很多时候弄懂样例，纸笔比在脑子里凭空想想，更有效。 //没感觉，翻看https://wenku.baidu.com/view/5b9dfd5abe23482fb4da4c40.html //直接dp，似乎说递推更确切点。 //f(i,k)表示经过k次传到编号为i的人手中的方案数。那么可以推出下面的方程： //f(i,k)=f(i-1,k-1)+f(i+1,k-1)（i=1或n时，需单独处理） //边界条件：f(1,0)=1;结果在f(1,m)中 //大致有些感觉，两个量，一是i人，二是k次 //编的过程中，发现下手有些困难，但之前有动态规划的经验，还是硬写下来，但样例没法通过 //手动模拟一编，发现问题，马上修改，样例通过，提交RE，翻看他人代码，才发现 //a=i-1;//1此处漏 //b=i+1;//1此处漏 //很小的两处问题。 #include <stdio.h> #include <string.h> int f[30+10][30+10]; int main(){ int n,m,i,j,a,b; scanf("%d%d",&n,&m); memset(f,0,sizeof(f)); f[1][0]=1; for(j=1;j<=m;j++) for(i=1;i<=n;i++){ a=i-1;//1此处漏 b=i+1;//1此处漏 if(i-1==0){ a=n; } else if(i+1>n) b=1; f[i][j]=f[a][j-1]+f[b][j-1]; } printf("%d ",f[1][m]); return 0; }
