机器人塔
原题目链接
题目描述
X 星球的机器人拉拉队有两种服装：A 和 B。
这次他们表演的是“搭机器人塔”，类似下图：
AB BA B AA A B BB B B A BA B A B B A
组塔规则：
- A 只能站在 AA 或 BB 的肩上；
- B 只能站在 AB 或 BA 的肩上。
输入描述
一行两个整数 M, N（0 < M, N < 500），分别表示 A 服和 B 服机器人的人数。输入保证人数合理，即存在至少一种合法搭塔方式。
输出描述
输出一个整数，表示可以搭成的合法塔的总数（即花样数量）。
输入样例
1 2
输出样例
3
c++代码
#include<bits/stdc++.h>using namespace std;typedef long long ll;ll M, N, k, ans = 0;
vector<char> recoder;ll dp(ll m, ll n) {vector<char> last = recoder, now(last.size() - 1);ll contm = 0,contn = 0;for (ll i = 0; i < k - 1; i++) {for (ll j = 0; j < now.size(); j++) {now[j] = last[j] == last[j + 1] ? 'A' : 'B';if (now[j] == 'A') contm++;else contn++;if (contm > m || contn > n) return 0;}last = now;now.pop_back();}return 1;
}void dfs(int m, int n) {if (recoder.size() == k) {ans += dp(M - m, N - n);return;}if (m <= M) recoder.push_back('A'), dfs(m + 1, n), recoder.pop_back();if (n <= N) recoder.push_back('B'), dfs(m, n + 1), recoder.pop_back();
}int main() {cin >> M >> N;k = (int)(sqrt(2 * (M + N) + 0.25) - 0.5);dfs(0, 0);cout << ans;return 0;
}//by wqs
思路解析
纯暴力题，枚举最后一层出现的情况，看这种情况合不合理就行。
