专栏文章

Meet in the middle 学习笔记

MMirage_Rover
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minhwzl1
此快照首次捕获于
2025/12/02 02:41
3 个月前
此快照最后确认于
2025/12/02 02:41
3 个月前
查看原文
「My Blog」
由于蒟蒻在模拟赛写 DFS 挂掉了，所以来学 Meet in the middle 。

「引入」

Meet in the middle 算法没有正式译名，常见的翻译为「折半搜索」、「双向搜索」或「中途相遇」，以下称折半搜索。
它适用于输入数据较小，但还没小到能直接使用暴力搜索的情况。
在普通 DFS 还在为难以通过 n≤20n\le 20 的数据点而抓耳挠腮时，我们折半搜索已经秒切 n≤40n\le 40 的数据点了。这么棒的算法你确定不学学吗？

「算法介绍」

折半搜索本质上是 DFS 的一种优化，它将搜索过程分成两半，分别计算后再将其结合，时间复杂度大大减少，将朴素 DFS 的 O(ab)O(a^b) 优化到了 O(ab/2)O(a^{b/2})。
这么讲可能有点抽象，让我们结合一道例题来深度讲解。

「例题」

洛谷 P4799 [CEOI 2015] 世界冰球锦标赛 (Day2)

给定 NN 场比赛的票价和预算 MM，计算总票价不超过 MM 的观赛方案数（不看任何比赛也算一种方案，选与不选某场比赛视为不同方案），其中 1≤N≤40，1≤M≤10181 \le N \le 40，1 \le M \le 10^{18}，票价不超过 101610^{16}。
先考虑朴素 DFS ，枚举每个比赛选或不选，时间复杂度 O(2N)O(2^N)，期望得分 40 pts40\ pts。

CodeCode

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[50],ans;
void dfs(int now,int sum){
	if(sum>m) return;
	if(now>n){
		ans++;
		return;
	}
	dfs(now+1,sum+a[now]);
	dfs(now+1,sum);
}
signed main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	dfs(1,0);
	cout<<ans;
	return 0;
}
提交记录
尝试在朴素 DFS 的基础上进行优化，首先，我们将门票价格均分成两半并分别进行搜索，并将搜索到的结果计入两个数组中。
CPP
vector<int> lf,rf; // 记录两次搜索的结果
void dfs1(int l,int r,int sum){
	if(sum>m) return;
	if(l>r){ // 与朴素 DFS 不同的点在于此处将 sum 计入搜索结果
		lf.push_back(sum);
		return;
	}
	dfs1(l+1,r,sum+a[l]);
	dfs1(l+1,r,sum);
}
void dfs2(int l,int r,int sum){
	if(sum>m) return;
	if(l>r){
		rf.push_back(sum);
		return;
	}
	dfs2(l+1,r,sum+a[l]);
	dfs2(l+1,r,sum);
}
接下来，我们将答案进行合并，对于答案数组 lflf，我们将其按从小到大的顺序排序，随后枚举答案数组 rfrf，每次二分找到第一个符合条件（设找到的 lflf 为 xx，当前枚举到了 rfrf 的第 ii 个数，则符合条件的 xx 需满足 lfx+rfi≤mlf_x+rf_i\le m）的 xx，不难想到所有下标 ≤x\le x 的答案也合法，所以将答案累加 xx。
CPP
sort(lf.begin(),lf.end());
	for(int i:rf){
		int rem=m-i;
		if(rem<0) continue;
		ans+=upper_bound(lf.begin(),lf.end(),rem)-lf.begin();
	}

完整代码

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[50],ans;
vector<int> lf,rf;
void dfs1(int l,int r,int sum){
	if(sum>m) return;
	if(l>r){
		lf.push_back(sum);
		return;
	}
	dfs1(l+1,r,sum+a[l]);
	dfs1(l+1,r,sum);
}
void dfs2(int l,int r,int sum){
	if(sum>m) return;
	if(l>r){
		rf.push_back(sum);
		return;
	}
	dfs2(l+1,r,sum+a[l]);
	dfs2(l+1,r,sum);
}
signed main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	int mid=(1+n)/2;
	dfs1(1,mid,0);
	dfs2(mid+1,n,0);
	sort(lf.begin(),lf.end());
	for(int i:rf){
		int rem=m-i;
		if(rem<0) continue;
		ans+=upper_bound(lf.begin(),lf.end(),rem)-lf.begin();
	}
	cout<<ans;
	return 0;
}
期望得分 100 pts100\ pts。

「总结」

好了，现在你已经学会折半搜索了，是不是很简单？
这边再推荐几道例题，有兴趣的读者可以再去看看。
洛谷 P1466 [USACO2.2] 集合 Subset Sums
洛谷 P10484 送礼物

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...