wordpress迁移站点,公司部门解散员工赔偿,学校网站维护,手机上做网站php题目描述 题目分析
由于数据小#xff0c;直接考虑DFS搜索底层所有排列组合。 我的代码
需要注意#xff1a;这个数据有点漏洞的是题干声明NM231#xff0c;但实际上有个测试点是等于231的。
一开始在build_tower#xff08;#xff09;函数中建完整个塔再判定是否…题目描述 题目分析
由于数据小直接考虑DFS搜索底层所有排列组合。 我的代码
需要注意这个数据有点漏洞的是题干声明NM231但实际上有个测试点是等于231的。
一开始在build_tower函数中建完整个塔再判定是否合格结果最大数据量下超时了。后面修改了函数每添加一个机器人就判定一次是否合格不合格直接退出函数这样运行时间就在有效时长内了。因此对于时间复杂度在极限附近的程序剪枝也是很有效的。
#include iostream
#include algorithm
#include cmath
using namespace std;
const int MAX_L22;
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 Am;int Bn; //构建底层 for(int i1;il;i){tower[l][i]bottom[i]; if(!bottom[i]) A--;if(bottom[i]) B--;}//构建上层for(int il-1;i0;i--){for(int j1;ji;j){tower[i][j]tower[i1][j]^tower[i1][j1]; //异或运算 if(!tower[i][j]) A--;if(tower[i][j]) B--;if(A0||B0) return;}}if(A0B0){ans;//数量正确 }
}
void dfs(int a,int b,int x){//a,b为剩余AB的数量 if(a0||b0||xl) return;if(xl){build_tower();return;}bottom[x1]0; dfs(a-1,b,x1); //0代表Abottom[x1]1;dfs(a,b-1,x1); //1代表B
}
int main()
{cinmn;for(int i1;i21;i){if(i*(i1)/2mn){li;}}ans0;dfs(m,n,0);coutans;return 0;
}
