传球游戏

1011. [NOIP2008] 传球游戏

http://cogs.pro/cogs/problem/problem.php?pid=1011

★   输入文件:ballg.in   输出文件:ballg.out   简单比较
岁月范围:1 s   内部存款和储蓄器限制:50 MB

【难点讲述】

上体育课的时候,小蛮的良师日常带着同学们一齐做游戏。此次,老师带着同学们齐声做传球游戏。

游戏规则是那样的:n个同学站成二个圆形,在那之中的二个同校手里拿着一个球,当老师吹哨辰时开首传球,各个同学能够把球传给协调左右的多少个同学中的1个(左右随意),当教员再一次吹哨马时,传球甘休,此时,拿着球没传出去的百般同学正是败者,要给大家表演两个节目。

驾驭的小蛮建议多个诙谐的难题:有微微种分歧的传球方法能够使得从小蛮手里起头传的球,传了m次以后,又赶回小蛮手里。三种传球的不二法门被用作差异的格局,当且仅当那两种方法中,接到球的校友按接球顺序组成的行列是不相同的。比如有1个同学1号、2号、3号,并要是小蛮为1号,球传了三次回到小蛮手里的措施有1->2->3->1和1->3->2->1,共2种。

 

【输入】

输入文件ball.in共一行,有多个用空格隔开分离的整数n,m(3<=n<=30,1<=m<=30)。

【输出】

出口文件ball.out共一行,有三个平头,表示符合题意的方法数。

 

【输入输出样例】

ball.in

ball.out

3 3

2

 

【限制】

五分之二的数目满足:3<=n<=30,1<=m<=20

百分之百的多寡满意:3<=n<=30,1<=m<=30

普及组一流简单的dp

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,f[40][40];
int main(){
    freopen("ballg.in","r",stdin);
    freopen("ballg.out","w",stdout);
    scanf("%d%d",&n,&m);
    f[0][1]=1;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            int pre=j-1;if(pre==0)pre=n;
            int nxt=j+1;if(nxt==n+1)nxt=1;
            f[i][j]=f[i-1][pre]+f[i-1][nxt];
        }
    }
    printf("%d",f[m][1]);
}

 

标题叙述

上体育课的时候,小蛮的老师日常带着同学们共同做游戏。这一次,老师带着同学们一道做传球游戏。

游戏规则是那样的:n个同学站成贰个圆形,个中的四个同室手里拿着一个球,当校官吹哨兔时起始传球,各个同学能够把球传给协调左右的七个同学中的1个(左右任意),当助教在此吹哨马时,传球停止,此时,拿着球没有传出去的万分同学正是败者,要给大家表演贰个节目。

智慧的小蛮提议3个妙不可言的题材:某些许种不相同的传球方法能够使得从小蛮手里开端传的球,传了m次现在,又再次来到小蛮手里。二种传球方法被看做不一样的点子,当且仅当那二种艺术中,接到球的同班按接球顺序组成的行列是分化的。比如有多少个同学1号、2号、3号,并假若小蛮为1号,球传了二次回到小蛮手里的艺术有1->2->3->1和1->3->2->1,共2种。

题材叙述

上体育课的时候,小蛮的助教平时带着同学们一道做游戏。这次,老师带着同学们一起做传球游戏。

游戏规则是那般的:n个同学站成多少个圆形,在那之中的二个同学手里拿着贰个球,当教员吹哨鸡时开头传球,每一个同学可以把球传给协调左右的七个同学中的一个(左右无限制),当教授再一次吹哨兔时,传球结束,此时,拿着球没有传出去的格外同学正是败者,要给大家表演三个剧目。

精明能干的小蛮提议三个妙趣横生的标题:有稍许种差别的传球方法能够使得从小蛮手里起初传的球,传了m次今后,又回去小蛮手里。三种传球方法被视作差异的法门,当且仅当那二种办法中,接到球的同学按接球顺序组成的种类是例外的。比如有八个同学1号、2号、3号,并借使小蛮为1号,球传了3次回到小蛮手里的办法有1->2->3->1和1->3->2->1,共2种。

输入输出格式

输入格式:

 

输入文件ball.in共一行,有七个用空格隔开分离的平头n,m(3<=n<=30,1<=m<=30)。

 

出口格式:

 

输出文件ball.out共一行,有三个平头,表示符合题意的法门数。

 

输入输出格式

输入格式:

 

输入文件ball.in共一行,有七个用空格隔开的平头n,m(3<=n<=30,1<=m<=30)。

 

出口格式:

 

出口文件ball.out共一行,有八个整数,表示符合题意的方式数。

 

输入输出样例

输入样例#1:

3 3

输出样例#1:

2

输入输出样例

输入样例#1:

3 3

输出样例#1:

2

说明

百分之四十的数码满意:3<=n<=30,1<=m<=20

百分百的数据满足:3<=n<=30,1<=m<=30

二零零六普及组第贰题

/*f[i][k]=f[i-1][k-1]+f[i+1][k-1],(i=1或n时,需单独处理)。
  边界条件:f[1][0]=1(特别注意);结果在f[1][m]中。*/

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

int i,j,k,n,m,f[31][31];

int main()
{ 
   scanf("%d%d",&n,&m);
   f[1][0]=1;
   for(k=1;k<=m;k++)
   {  
         f[1][k]=f[2][k-1]+f[n][k-1];
      for(i=2;i<=n-1;i++)f[i][k]=f[i-1][k-1]+f[i+1][k-1];
         f[n][k]=f[n-1][k-1]+f[1][k-1];
   }
   printf("%d",f[1][m]);
   return 0; 
}

 

 

说明

百分之四十的多少满足:3<=n<=30,1<=m<=20

百分之百的数码满足:3<=n<=30,1<=m<=30

二〇〇八普及组第一题

 

dp[i][j] 表示第i轮 球在j那里

方程dp[i][j]=dp[i-1][j%n+1]+dp[i-1][j-1==0?n:j-1];

屠龙宝刀点击就送

#include <cstdio>

int dp[31][31],n,m;
int Main()
{
    scanf("%d%d",&n,&m);
    dp[0][1]=1;
    for(int i=1;i<=m;++i)
     for(int j=1;j<=n;++j)
      dp[i][j]=dp[i-1][j%n+1]+dp[i-1][j-1==0?n:j-1];
    printf("%d\n",dp[m][1]);
    return 0;
}
int sb=Main();
int main(int argc,char *argv[]){;}

 

相关文章