Meet in the middle，或称折半搜索，是一种搜索的优化方法．

折半搜索用于普通的搜索数据量过大，可以将时间复杂度中的变量减半．

使用折半搜索，有以下几步：

确认一个起点，一个终点
由起点开始搜索，但是不要搜索完全，只需要进行一半的决策，记录下状态．
由终点开始反着搜索，倒着进行一半的决策，如果所得的状态在第二步中有记录，那么则可以将其作为答案（或答案的一个贡献）．

使用朴素搜索，如果有 $n$ 个决策点，每个决策点有 $m$ 个选择，则其时间复杂度为 $O(m^n)$ ，如果使用折半搜索，那么时间复杂度会降为 $O(m^{\frac{n}{2}})$

例题#

有 $n$ 个灯泡，每个灯泡有亮和暗两种状态，初始每一盏灯都是暗的．
你可以对一盏灯进行一次操作，使得其改变状态（即亮的灯变暗，暗的灯变量）．与此同时，每一盏灯还有它的伴随灯，当你对灯泡 $i$ 进行操作时，所有灯泡 $i$ 的伴随灯 $p_{i,j}$ 都会改变状态，但是 $p_{i,j}$ 的伴随灯不会改变状态．
你需要将所有灯都变成亮的，求最小操作次数．

输入格式

第一行一个正整数 $n$ ，表示一共的灯泡数量

接下来 $n$ 行，第 $i$ 行先有一个整数 $k_i$ ，表示灯泡 $i$ 的伴随灯数量，接下来 $k_i$ 个整数，表示灯泡 $i$ 的所有伴随灯编号．

输出格式

一行一个整数，表示最小的操作数．

数据约束

对于 $50\%$ 的数据， $n \leq 18$

对于 $100\%$ 的数据， $n \leq 35$ ，且对于所有的 $i$ （ $1\leq i\leq n$ ），都有 $k_i \lt n$

分析#

50pts 的做法很简单，只需要从全部都是暗的开始 DFS 搜索，对于每一盏灯，都有操作和不操作两种状态（对一盏灯操作两次等同于没操作），这样依次对每一盏灯进行决策．可以传递一个参数 $s$ ， $s$ 的二进制的从低到高第 $i$ 为表示第 $i$ 盏灯亮（用 1 表示）还是灭（用 0 表示），直到所有灯都决策完后，如果 $s$ 的每一位都是 1，那么将这种开关方式算作合法的开关方式，将操作次数记录．这种解决问题方式的复杂度是 $O(2^n)$

那么如何解决这道题呢？使用折中搜索．

首先，确定起点和终点，起点是全部灯都是暗的，此时 $s$ 的所有位都是 0．终点是全部灯都是亮的，此时 $s$ 的所有位都是 1．

而后，我们进行第一次 DFS，在这第一次中，我们将前 $\lceil\frac{n}{2}\rceil$ 个灯泡进行决策，将决策结果记录在一个 map 中，map 的键是状态 $s$ ，map 的值是前 $\lceil\frac{n}{2}\rceil$ 个灯泡中选择操作的数量．

最后，我们从全部灯都是亮的的状态进行一次倒着的 DFS，我们将后 $\lfloor\frac{n}{2}\rfloor$ 个灯泡进行决策，将决策后的状态 $s$ 放在 map 中比较，看有没有对应的状态，如果有，将前后两次的操作次数相加，作为一种可行的方案，最后在所有可行的方案中，取操作数量最少的一个．

这种想法的时间复杂度是 $O(2^{\frac{n}{2}})$ ，可以通过．