A40844. 机器人塔
填空题
困难
知识点
题目描述
机器人塔
题目描述
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
参考答案
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;
int num_a, num_b, line;
char map[45][45];
long long ans;
bool check() {
int a = 0, b = 0;
for (int i = 1; i < line + 1; i++)
for (int j = 1; j < i + 1; j++)
if (map[i][j] == 'A') a++;
else b++;
if ((a != num_a) || (b != num_b)) return false;
return true;
}
void init() {
for (int i = line; i > 1; i--)
for (int j = 1; j < i; j++)
if (map[i][j] == map[i][j + 1])
map[i - 1][j] = 'A';
else map[i - 1][j] = 'B';
}
void dfs(int y) {
if (y == line + 1) {
init();
if (check()) {
ans++;
}
return;
}
map[line][y] = 'A';
dfs(y + 1);
map[line][y] = 'B';
dfs(y + 1);
}
int main() {
cin >> num_a >> num_b;
int temp = sqrt(1 + 8 * (num_a + num_b));
line = (temp - 1) / 2;
dfs(1);
cout << ans << endl;
return 0;
}
上一题
下一题