简介
折半搜索是一种优化搜索的方法,一般可以将 \(O(2^N)\) 优化为 \(O(2^{\frac{N}{2}})\) 。其思想为将一个搜索拆分成两个搜索,分别处理前一半和后一半,使用 map
或 vector
等东西记录第一次搜索的信息,在第二次搜索时查询。
如以下代码:
void dfs(int x, int sum) {
if(x > k) {
return;
}
if(x > n) {
ans += (sum == k);
return;
}
dfs(x + 1, sum);
dfs(x + 1, sum + a[x]);
}
dfs(1, 0);
用折半搜索会这么写
void dfs(int x, int sum) {
if(x > k) {
return;
}
if(x == mid + 1) {
mp[sum]++;
return;
}
dfs(x + 1, sum);
dfs(x + 1, sum + a[x]);
}
void dfs2(int x, int sum) {
if(x > k) {
return;
}
if(x == n + 1) {
ans += mp[k - sum];
return;
}
dfs2(x + 1, sum);
dfs2(x + 1, sum + a[x]);
}
mid = n / 2, dfs(1, 0), dfs2(mid + 1, 0);
标签:折半,return,int,sum,dfs,搜索
From: https://www.cnblogs.com/yaosicheng124/p/18158124