欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

折半搜索 [meet in the middle]

程序员文章站 2024-03-12 15:54:44
...

Learning

在使用搜索的时候,当n过大2n会超时,这时候可以用折半搜索,把时间复杂度降低到2n/2+1
折半搜索 [meet in the middle]
具体方法:分别搜索前一半,把状态放入a数组,搜索后一半,把状态放入b数组,最后统计答案。
一般meet in the middle的难点主要在于最后答案的组合统计。
我们可以现将a或b数组sort,让其有序。然后通过枚举另一个数组中的状态,来实现统计答案。折半搜索 [meet in the middle]


Practice

[洛谷 4799] 世界冰球锦标赛

题目链接

题意:给定n(<=40)场比赛门票各自的价格,和Bobek拥有的钱数,求观赛方案总数。
(如果存在以其中一种方案观看某场比赛而另一种方案不观看,则认为这两种方案不同。可以一场也不看)

思路:240的搜索肯定会超时,所以折半搜索。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=1<<21;
ll m,ans,a[50],suma[MAXN],sumb[MAXN];
int n,cnta,cntb;
void dfs(int t,int M,ll f[],ll s,int &cnt){
	if(t==M+1){
		f[++cnt]=s;
		return;
	}
	dfs(t+1,M,f,s,cnt);
	dfs(t+1,M,f,s+a[t],cnt);
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	int k=(1+n)/2,d;
	dfs(1,k,suma,0,cnta);//搜索前一半
	dfs(k+1,n,sumb,0,cntb);//搜索后一半
	sort(sumb+1,sumb+1+cntb);//合并
	for(int i=1;i<=cnta;i++){
		d=upper_bound(sumb+1,sumb+1+cntb,m-suma[i])-sumb-1;
		ans+=d;
	}
	cout<<ans;
}

[洛谷 3067] Balanced Cow Subsets

题目链接

题意:给n(<=20)个数,从中任意选出一些数,使这些数能分成和相等的两组。求有多少种选数的方案。

思路:这道题有三种状态:①不放入任何集合 ②放入左边集合 ③放入右边集合
[面向题解设计程序。。一知半解]

#include<cstdio>
#include<cmath>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
using namespace std;
#define ll long long
int n,mid;
struct node{
	int v,f;
}suma[1<<22],sumb[1<<22];
int cnta,cntb,m[44],r;
bool vis[1<<23];
ll ans;
void dfs(int l,int flag,int sum,int t){
	if(l>r){
		if(t){
			suma[++cnta].v=sum;
			suma[cnta].f=flag;
		}else{
			sumb[++cntb].v=sum;
			sumb[cntb].f=flag;
		}
		return;
	}
	dfs(l+1,flag,sum,t);
	dfs(l+1,flag+(1<<(l-1)),sum+m[l],t);
	dfs(l+1,flag+(1<<(l-1)),sum-m[l],t);
}
inline bool cmp1(node x,node y){return x.v<y.v;}
inline bool cmp2(node x,node y){return x.v>y.v;}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)scanf("%d",&m[i]);
	mid=(1+n)/2;
	r=mid;dfs(1,0,0,1);//折半搜索 
	r=n;dfs(mid+1,0,0,0);
	
	sort(suma+1,suma+1+cnta,cmp1);//排序 
	sort(sumb+1,sumb+1+cntb,cmp2);
	
	int l=1,r=1;
	while(l<=cnta&&r<=cntb){//双指针
		while(-suma[l].v<sumb[r].v&&r<=cntb)r++;
		int p=r;
		while(r<=cntb&&-suma[l].v==sumb[r].v){
			if(!vis[suma[l].f|sumb[r].f]){
				vis[suma[l].f|sumb[r].f]=1;
				ans++;
			}
			r++;
		}
		if(l<cnta&&suma[l].v==suma[l+1].v)r=p;
		l++;
	}
	cout<<ans-1;
}
	
	
	
相关标签: 算法和数据结构