第七届蓝桥杯C/C++程序设计本科B组决赛 —

机器人塔

X星球的机器人表演拉拉队有两种服装，A和B。
他们这次表演的是搭机器人塔。

类似：

A
B B
A B A
A A B B
B B B A B
A B A B B A

队内的组塔规则是：

A 只能站在 AA 或 BB 的肩上。
B 只能站在 AB 或 BA 的肩上。

你的任务是帮助拉拉队计算一下，在给定A与B的人数时，可以组成多少种花样的塔。

输入一行两个整数 M 和 N，空格分开（0<M,N<500）,分别表示A、B的人数，保证人数合理性。

要求输出一个整数，表示可以产生的花样种数。

例如：
用户输入：
1 2

程序应该输出：
3

再例如：
用户输入：
3 3

程序应该输出：
4

题目思路：

　　搜索，先枚举最后一层，然后逐层往上迭代，看是否AB够用，够用则ans++。

　　如下代码大概能水一些小数据吧——

　　（1、把正三角形，改成了等腰直角三角形，更便于遍历；2、先计算出层数，然后底层确定后上面必定是唯一的局面，全部遍历判断即可！）

 #include <stdio.h>

 #include <stdlib.h>

 #include <iostream>

 #include <algorithm>

 #include <queue>

 #include <stack>

 #include <vector>

 #include<math.h>

 #include <string.h>

 #include<set>

 using namespace std;

 #define inf 0x3f3f3f3f

 #define maxn 10000000

 const double pi=acos(-1.0);

 #define ll long long

 #define N 108

 using namespace std;

 double fact(double a,double b,double c){

     double y=sqrt(-*a*c);

     double s=(-b+y)/2.0;

     return s;

 }

 ll ans=;

 int a[N][N];

 int flag;

 void build(int step,int anum,int bnum,int mstep){

     if(anum<||bnum<){

         return ;

    }

    if(step==-){

         flag=;return ;

    }

    for(int i=;i<=step;i++){

         if(a[step+][i]==a[step+][i+] ){

             a[step][i]=;anum--;

         }

         else a[step][i]=,bnum--;

    }

     build(step-,anum,bnum,mstep);

    return ;

 }

 void dfs(int step,int pos,int anum,int bnum,int mstep){//枚举step行的存储数据，然后往上搭建看看

    if(anum<||bnum<){

         return ;

    }

    if(pos==step+){

         flag=;

         build(step-,anum,bnum,mstep);//按照最后一行进行搭建

         ans+=flag;

         return ;

    }

    for(int i=;i<=;i++){

         a[step][pos]=i;

         if(i==)

             dfs(step,pos+,anum,bnum-,mstep);

         else

             dfs(step,pos+,anum-,bnum,mstep);

    }

 }

 int main(){

     int m,n;//分别表示A、B的人数

     while(scanf("%d%d",&m,&n)!=EOF){

          int x=(int)fact(1.0,1.0,-2.0*(m+n));//表示层数

          printf("总行数=%d\n",x);

         ans=;

         memset(a,-,sizeof(a));

         dfs(x,,m,n,x);

         printf("%lld\n",ans);

     }

     return ;

 }

巴特西

第七届蓝桥杯C/C++程序设计本科B组决赛 ——机器人塔(程序大题)

机器人塔

题目思路：

最新文章

热门文章