在深度优先搜索中，我们通过暴力枚举每种可行的情况并进行剪枝可以得到答案，这种做法的时间复杂度是 O(2^n\times A)，A 是任意关于 n 的多项式，这个时间复杂度非常高，在 n\geq 30 时，若多项式 A 的运算量稍高，即使进行了十分恰当的剪枝，也难以通过，那么，如果现在我们的数据范围来到了 40\sim 50，我们需要使用其他的优化方法，那么，“Baby, what if we could meet in the middle?”，meet in the middle（折半搜索）的思想成为了不错的选择。
meet in the middle 的思想就是在 dfs 或者暴力枚举区间 [l,r] 时，先将答案折半，取其中间值 mid={l+r}\over 2，并且对区间 [l,mid] 和 [mid+1,r] 进行分别枚举，最后前一半和后一半将符合条件的情况进行合并即可。
如何 meet in the middle？
看完上述对 meet int the middle 的介绍，我们来详细讲讲如何前后分别枚举，如何合并两区间中的答案以得到最终答案。
★ 先来看一个例题：
给定 n 个格子每个格子有高度 h_i 和权值 w_i。
你每次可以从任意一个格子开始，向右跳到任意一个高度不低于当前格子的位置，可以在任意位置停止。
给定一个限制 m，求出最后经过权值总和 \geq k 的方案数。
对于 $40\%$ 的数据，$n\leq 20$，
对于 $100\%$ 的数据，$n\leq 40$。
显然，$40\%$ 的分数是很好拿的，只要写一个简单的 dfs 暴力枚举一下就好了，但是如果我们想拿满分，就不那么容易了。
考虑将整个区间分成两部分，$[1,\lfloor{{n+1}\over 2}\rfloor]$ 和 $[\lfloor{{n+1}\over 2}\rfloor+1,n]$，这样的话，时间复杂度就大大降低了，但是，对于两侧分别 $dfs$ 以后，就难以继续下去了，所以我们如何将两边的答案合并呢？
首先，计算前一半的答案，记录到 vector 当中，但是要注意的是，如果只搜前一半答案就已经大于等于 $m$ 了，就直接将答案加一，代码如下（详细注释在代码中）：
```cpp
vector<int> v[43]; //存答案的 vector
long long h[43], w[43]; //高度和权值
long long n, m, res = 0; //记录n,m和答案
void dfs(int id, int k, int lim) {
k += w[id]; //增加现在的权值
v[id].push_back(k); //将搜索到的值加入vector中
if (k >= m) res++; //如果已经大于m，那么直接增加答案
for (int i = id + 1; i <= lim; ++i)
if (h[i] >= h[id]) //高度限制
dfs(i, k, lim); //递归搜索
}
```
首先，计算后一半的答案，如果搜索到当前位置时已经有的权值为 $w$，那么我们就需要找在前一半中，权值大于等于 $m-w$，且结束高度小于等于我们后一半的起始高度的数量，这个操作可以直接在 vector 中用 lower_bound 二分快速查询。还是要注意，如果只搜前一半答案就已经大于等于 $m$ 了，就直接将答案加一，并且为了便于判断起始高度与结束高度的大小关系，我们从后向前，也就是从 $n$ 向 $mid+1$ 进行搜索，代码如下（详细注释在代码中）：
```cpp
void query(int id, int t, int lim) {
int k = t + w[id]; //增加现在的权值
if (k >= m) res++; //如果已经大于m，那么直接增加答案
for (int i = 1; i <= lim; ++i)
if (h[i] <= h[id]) //对于每个起始高度大于等于结束高度的vector
res += v[i].end() - lower_bound(v[i].begin(), v[i].end(), m - k); //二分查找
for (int i = id - 1; i > lim; --i) //注意这里从后往前搜
if (h[i] <= h[id]) //高度限制
query(i, k, lim); //继续递归搜索
}
```
最后在 main() 函数中输出答案：
```cpp
int main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> h[i] >> w[i];
int l = n >> 1;
for (int i = 1; i <= l; ++i) dfs(i, 0, l);
for (int i = 1; i <= l; ++i) sort(v[i].begin(), v[i].end());
for (int i = l + 1; i <= n; ++i) query(i, 0, l);
cout << res << '\n';
return 0;
}
```
我们就使用 meet in the middle 解决了这道题目!
总结一下，meet in the middle 的关键就在于首先取 middle，然后分段，最后再 "take a leap to the middle" 即可，用十个字概括其思想为 **前一半枚举，后一半查询**！
当然，meet in the middle 也不一定必须用在 dfs 或状态压缩 dp 中。