Meet in the middle 学习笔记

· · 算法·理论

「My Blog」

由于蒟蒻在模拟赛写 DFS 挂掉了，所以来学 Meet in the middle 。

「引入」

Meet in the middle 算法没有正式译名，常见的翻译为「折半搜索」、「双向搜索」或「中途相遇」，以下称折半搜索。

它适用于输入数据较小，但还没小到能直接使用暴力搜索的情况。

在普通 DFS 还在为难以通过 n\le 20 的数据点而抓耳挠腮时，我们折半搜索已经秒切 n\le 40 的数据点了。这么棒的算法你确定不学学吗？

「算法介绍」

折半搜索本质上是 DFS 的一种优化，它将搜索过程分成两半，分别计算后再将其结合，时间复杂度大大减少，将朴素 DFS 的 O(a^b) 优化到了 O(a^{b/2})。

这么讲可能有点抽象，让我们结合一道例题来深度讲解。

「例题」

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

给定 N 场比赛的票价和预算 M，计算总票价不超过 M 的观赛方案数（不看任何比赛也算一种方案，选与不选某场比赛视为不同方案），其中 1 \le N \le 40，1 \le M \le 10^{18}，票价不超过 10^{16}。

先考虑朴素 DFS ，枚举每个比赛选或不选，时间复杂度 O(2^N)，期望得分 40\ pts。

Code

#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 的基础上进行优化，首先，我们将门票价格均分成两半并分别进行搜索，并将搜索到的结果计入两个数组中。

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);
}

接下来，我们将答案进行合并，对于答案数组 lf，我们将其按从小到大的顺序排序，随后枚举答案数组 rf，每次二分找到第一个符合条件（设找到的 lf 为 x，当前枚举到了 rf 的第 i 个数，则符合条件的 x 需满足 lf_x+rf_i\le m）的 x，不难想到所有下标 \le x 的答案也合法，所以将答案累加 x。

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();
    }

完整代码

#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\ pts。

「总结」

好了，现在你已经学会折半搜索了，是不是很简单？

这边再推荐几道例题，有兴趣的读者可以再去看看。

洛谷 P1466 [USACO2.2] 集合 Subset Sums

洛谷 P10484 送礼物