个人博客模板网站,照片编辑软件app,贵阳网站开发制作公司,宝安网页设计DFS剪枝 其实就是将搜索过程一些不必要的部分直接剔除掉。 剪枝是回溯法的一种重要优化手段#xff0c;往往需要先写一个暴力搜索#xff0c;然后找到某些特殊的数学关系#xff0c;或者逻辑关系#xff0c;通过它们的约束让搜索树尽可能浅而小#xff0c;从而达到降低时间… DFS剪枝 其实就是将搜索过程一些不必要的部分直接剔除掉。 剪枝是回溯法的一种重要优化手段往往需要先写一个暴力搜索然后找到某些特殊的数学关系或者逻辑关系通过它们的约束让搜索树尽可能浅而小从而达到降低时间复杂度的目的。 示例 分析 n-[1,10]数据范围并不是很大我们可以考虑枚举所有答案来找到这个最合适的队伍数量。 就比如说我现在有n个人那么最多的队伍数量肯定不超过n所以我们可以从只有1个队伍枚举到有n个队伍肯定能找到其中一种方案符合题意。当时由于一个队伍中不能有处于倍数关系的整数所以我们可以使用剪枝做优化在一开始就判断如果不符合题意就排除掉提高效率。
#includebits/stdc.h
using namespace std;
const int N 1e55;
int n;
int a[N];
vectorint v[N];
int dfs(int cnt,int dep){if(depn1){return true;}for(int i1;icnt;i){bool tagtrue;for(const autoj:v[i]){if(a[dep]%j0){tagfalse;break; }}if(!tag)continue;v[i].push_back(a[dep]);if(dfs(cnt,dep1))return true;//恢复现场 v[i].pop_back();}return false;
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cinn;for(int i1;in;i)cina[i];for(int i1;in;i){if(dfs(i,1)){ //有i个队伍第1层出发 couti\n;break;}}return 0;
}
