[蓝桥杯][2015年第六届真题]机器人塔(dfs)
2024-10-20 13:31:26
题目描述
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的人数,保证人数合理性。
要求输出一个整数,表示可以产生的花样种数。
输入
输入一行两个整数 M 和 N,空格分开(0<M,N<500),分别表示A、B的人数,保证人数合理性。
输出
要求输出一个整数,表示可以产生的花样种数。
样例输入
1 2
样例输出
3
提示
无
来源
无
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<vector>
#include<cmath>
const int maxn=1e5+5;
typedef long long ll;
using namespace std;
int a[50][50];
int k=1;
int vis[55];
int s=0;
int n,m;
void dfs(int x)
{
if(x==k)
{
for(int j=k-2;j>=0;j--)
{
for(int kk=0;kk<=j;kk++)
if((a[j+1][kk]==0&&a[j+1][kk+1]==1)||(a[j+1][kk]==1&&a[j+1][kk+1]==0))
{
a[j][kk]=1;
}
else
{
a[j][kk]=0;
}
}
int s1=0;
int s2=0;
for(int t=0;t<k;t++)
{
for(int j=0;j<=t;j++)
{
if(a[t][j]==0)
{
s1++;
}
else
{
s2++;
}
}
}
if(s1==n&&s2==m)
{
s++;
}
return ;
}
if(vis[x]==0)
{
vis[x]=1;
a[k-1][x]=1;
dfs(x+1);
a[k-1][x]=0;
dfs(x+1);
vis[x]=0;
}
}
int main()
{
cin>>n>>m;
int sum=0;
while(sum+k<n+m)
{
sum+=k;
k++;
}
dfs(0);
cout<<s<<endl;
return 0;
}
最新文章
- QT特供 CGAL配置流程(基于QT5+VS2015)
- oracle JOB学习(一)---基础
- WindowsPhone-GameBoy模拟器开发四--Gameboy显示系统分析
- Sprint第一个冲刺(第十一天)
- 【性能测试】性能测试总结<;二>;
- Windows phone 8 学习笔记(7) 设备(转)
- 浅析CSS负边距
- 李洪强iOS开发之【Objective-C】09-空指针和野指针
- python学习之 dictionary 、list、tuple操作
- perl 使用use utf8
- 【Android进阶】SlidingMenu实现侧滑栏效果的实现
- java计数器CountDownLatch
- 17、手把手教你Extjs5(十七)模块的新增、修改、删除操作
- Java synchronized 关键字的实现原理
- C#基础语法
- Tensorflow 报错:tensorflow.python.framework.errors_impl.InternalError: Failed to create session.
- Holer实现外网访问本地MySQL数据库
- Linux基本指令
- 实践中 XunSearch(讯搜)的使用教程步骤
- Vue -- 数据监听