机器人塔
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、先计算出层数,然后底层确定后上面必定是唯一的局面,全部遍历判断即可!)
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <iostream>
4 #include <algorithm>
5 #include <queue>
6 #include <stack>
7 #include <vector>
8 #include<math.h>
9 #include <string.h>
10 #include<set>
11 using namespace std;
12 #define inf 0x3f3f3f3f
13 #define maxn 10000000
14 const double pi=acos(-1.0);
15 #define ll long long
16 #define N 108
17 using namespace std;
18 double fact(double a,double b,double c){
19 double y=sqrt(1-4*a*c);
20 double s=(-b+y)/2.0;
21 return s;
22 }
23 ll ans=0;
24 int a[N][N];
25 int flag;
26 void build(int step,int anum,int bnum,int mstep){
27 if(anum<0||bnum<0){
28 return ;
29 }
30 if(step==-1){
31 flag=1;return ;
32 }
33 for(int i=1;i<=step;i++){
34 if(a[step+1][i]==a[step+1][i+1] ){
35 a[step][i]=1;anum--;
36 }
37 else a[step][i]=0,bnum--;
38 }
39 build(step-1,anum,bnum,mstep);
40
41 return ;
42 }
43 void dfs(int step,int pos,int anum,int bnum,int mstep){//枚举step行的存储数据,然后往上搭建看看
44 if(anum<0||bnum<0){
45 return ;
46 }
47 if(pos==step+1){
48 flag=0;
49 build(step-1,anum,bnum,mstep);//按照最后一行进行搭建
50 ans+=flag;
51 return ;
52 }
53 for(int i=0;i<=1;i++){
54 a[step][pos]=i;
55 if(i==0)
56 dfs(step,pos+1,anum,bnum-1,mstep);
57 else
58 dfs(step,pos+1,anum-1,bnum,mstep);
59 }
60 }
61 int main(){
62 int m,n;//分别表示A、B的人数
63 while(scanf("%d%d",&m,&n)!=EOF){
64 int x=(int)fact(1.0,1.0,-2.0*(m+n));//表示层数
65 printf("总行数=%d\n",x);
66 ans=0;
67 memset(a,-1,sizeof(a));
68 dfs(x,1,m,n,x);
69 printf("%lld\n",ans);
70 }
71
72
73 return 0;
74 }
View Code
|
请发表评论