【2024.10.22练习】机器人塔

题目描述

---

题目分析

由于数据小，直接考虑DFS搜索底层所有排列组合。

---

我的代码

需要注意：这个数据有点漏洞的是题干声明N+M<231，但实际上有个测试点是等于231的。

一开始在build_tower（）函数中建完整个塔再判定是否合格，结果最大数据量下超时了。后面修改了函数，每添加一个机器人就判定一次是否合格，不合格直接退出函数，这样运行时间就在有效时长内了。因此对于时间复杂度在极限附近的程序，剪枝也是很有效的。

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAX_L=22;
int m; //A数量 
int n; //B数量
int l; //层数:也是最底层的机器人数 
bool bottom[MAX_L];//最底层机器人排列 
bool tower[MAX_L][MAX_L]; 
//tower[i][j]表示第i层从左往右第j个机器人种类 
int ans;
void build_tower(){//记录用于构筑的A,B数量int A=m;int B=n; //构建底层 for(int i=1;i<=l;i++){tower[l][i]=bottom[i]; if(!bottom[i]) A--;if(bottom[i]) B--;}//构建上层for(int i=l-1;i>0;i--){for(int j=1;j<=i;j++){tower[i][j]=tower[i+1][j]^tower[i+1][j+1]; //异或运算 if(!tower[i][j]) A--;if(tower[i][j]) B--;if(A<0||B<0) return;}}if(A==0&&B==0){ans++;//数量正确 }
}
void dfs(int a,int b,int x){//a,b为剩余A，B的数量 if(a<0||b<0||x>l) return;if(x==l){build_tower();return;}bottom[x+1]=0; dfs(a-1,b,x+1); //0代表Abottom[x+1]=1;dfs(a,b-1,x+1); //1代表B
}
int main()
{cin>>m>>n;for(int i=1;i<=21;i++){if(i*(i+1)/2==m+n){l=i;}}ans=0;dfs(m,n,0);cout<<ans;return 0;
}