本文主要是介绍搜索＜3＞——折半搜索(meet in the middle)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
我上网一搜折半搜索，结果跳出来的为什么全是二分??????????????????????????气死我了。
回归正题，折半搜索指将整个搜索过程分为两部分，并对两部分分别进行搜索，最后得到两个答案序列，将这两个答案序列进行合并，得到最终的答案。这样可以大大降低复杂度，比如原来的这样就变成了
。来看一些题吧。
P4799:
很经典的题目了。首先，可以状压枚举每种情况，但是TLE，所以考虑折半搜索。将前一半的搜索状态存入a数组，后一半存入b数组。难点主要在于最后答案的组合统计。我们可以现将a或b数组sort，然后通过枚举另一个数组中的状态，来实现统计答案。令pos为当前枚举的x的第一个
，那么在pos之前的位置都可以贡献答案，所以ans+=pos-1。那么找pos的工程可以用upper_bound()实现。
#include <bits/stdc++.h>
using namespace std;
vector<int> l,r;
long long ticket[100];
long long n,m,mid;
void dfs1(long long step, long long cost){if(cost>m)return;if(step>mid){l.push_back(cost); return;}dfs1(step+1,cost+ticket[step]);dfs1(step+1,cost);
}
void dfs2(long long step, long long cost){if(cost>m)return;if(step>n){r.push_back(cost); return;}dfs2(step+1,cost+ticket[step]);dfs2(step+1,cost);
}
int main(){cin>>n>>m;mid=(n+1)>>1;for(long long i=1;i<=n;i++)cin>>ticket[i];dfs1(1,0); dfs2(mid+1,0);sort(r.begin(),r.end());long long ans=0;for(auto x:l)ans+=upper_bound(r.begin(),r.end(),m-x)-r.begin();cout<<ans<<endl;return 0;
}P3067:
很不显然，这题比世界冰球锦标赛难一些。
当然，上来考虑(有3种状态:不放入任何集合，放入左边，放入右边)暴力，但显然大于1E9，你会得到一个完美的TLE。在搜索时我们可以0,1,-1来表示，像这样↓
dfs(dep+1,sum);
dfs(dep+1,sum+a[dep]);
dfs(dep+1,sum-a[dep]);但是我们得到的答案可能会有重复，因为我们可能把一个数选入左集合或右集合，但是都加入了状态，所以我们需要判重。所以搜索时还要去记录状态，用一个vis数组判重。
if(!vis[a[l].sta|b[r].sta])vis[a[l].sta|b[r].sta]=1;//sta记录二进制的选数状态 1表示选 0表示没选最后要统计答案，排序后双指针扫描一遍即可。
#include <bits/stdc++.h>
using namespace std;
int n,a[50],cntl,cntr,ans;
bool vis[1<<22];
struct node{int sta,val;
}l[1<<22],r[1<<22];
bool cmpl(node x,node y){return x.val<y.val;
}
bool cmpr(node x,node y){return x.val>y.val;
}
void dfs1(int x,int tot,int sta){if(x>(n>>1)){cntl++;l[cntl]=node{sta,tot};return;}dfs1(x+1,tot,sta);dfs1(x+1,tot+a[x],sta|(1<<(x-1)));dfs1(x+1,tot-a[x],sta|(1<<(x-1)));
}
void dfs2(int x,int tot,int sta){if(x>n){cntr++;r[cntr]=node{sta,tot};return;}dfs2(x+1,tot,sta);dfs2(x+1,tot+a[x],sta|(1<<(x-1)));dfs2(x+1,tot-a[x],sta|(1<<(x-1)));
}
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];dfs1(1,0,0);dfs2((n>>1)+1,0,0);sort(l+1,l+cntl+1,cmpl);sort(r+1,r+cntr+1,cmpr);for(int i=1,j=1,pos;i<=cntl && j<=cntr;i++){while(j<=cntr && l[i].val+r[j].val>0)j++;for(pos=j;l[i].val==-r[pos].val;pos++){int sta=(l[i].sta|r[pos].sta);if(!vis[sta]){vis[sta]=1；ans++;}}}cout<<ans<<endl;return 0;
}注意，最后别忘了把0的那种方案减去。(我没减是因为ans设为-1，已经被我改了)
以上就是本期的全部内容了，我们下期再见!
温馨提示:本期的全部代码都有问题，请不要无脑Ctrl C+Ctrl V
这篇关于搜索＜3＞——折半搜索(meet in the middle)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
