题目链接

https://www.dotcpp.com/oj/problem1837.html

题目大意

输入两个数，m，n分别代表A的数量和B的数量；
构建一个人塔，要求A脚底下的两个字母必须是A和A或者B和B，即脚底两个字母相同，B脚底下的两个字母必须是A和B或者B和A，即脚底两个字母不相同；
输出能排列出的种类数量。

解题思路

我的思路比较直白（傻），二进制枚举，枚举最底下一行的排列状态。最底下一行的排列状态确定后，上面的排列状态也就确定了，所以，只要统计构建的人塔中A和B的数量是否与输入相同，相同的话种类数+1。
什么是二进制枚举？以本题为例，每一个位置要么放A要么放B，这和二进制有点像啊，那就让A对应1，B对应0。
这样一来，1 1 0什么意思？A A B的意思吧。加入最底下一行有3个人，所有的可能，BBB，BBA，BAB，BAA，ABB，ABA，AAB，AAA，对应的二进制为，000，001，010，011，100，101，110，111，这不就是2^3吗。所以，最后一行的排列状态就可以通过循环表现出来了， for(int i=0;i<=(1<<3)-1;i++)

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=50;
int dp[N];//用一维数组表示二维状态，有点类似01背包问题优化的思想，但不是01背包！
int main(){
    int n,m,ans=0;
    cin>>m>>n;
    int h=(int)sqrt(2*(m+n));//计算出人塔的行数
    for(int num=0;num<=(1<<h)-1;num++){
        int tmp_h=h,tmp=num,cnt_a=0,cnt_b=0;
        for(int i=tmp_h;i>=1;i--,tmp>>=1){
            dp[i]=tmp&1;//初始化最底下一行
            if(dp[i]) cnt_a++;
            else cnt_b++;
        }

        while(tmp_h--){
            for(int i=1;i<=tmp_h;i++){
                if(dp[i+1] == dp[i]) cnt_a++,dp[i]=1;//set A
                else cnt_b++,dp[i]=0;//set B
            }
        }
        if(cnt_a==m && cnt_b==n) ans++;
    }
    cout<<ans<<endl;
}