前言
搜索本身就是一种布鲁特佛斯(Brute-Force)算法，所以它的优化是十分重要的，其中一种就是折半搜索。
正文
折半搜索的主要思想是：对于一类搜索问题，将本来直接搜索的算法转换成分别搜索两部分，再把两部分结果组合得到最终答案。通常这两部分大小相等，但有时候碍于空间或者时间限制，需要微调。
例题1
JZOJ 4841
JZOJ 4841
我们可以给每个人一个权值，这个权值可以是\{0,1,-1\}，分别的意思是：
0：这个人不取出来。
1：这个人取出来分到1队。
-1：这个人取出来分到2队。
问题就变成了给每个人分配三个权值中的一个，和为0的方案数。
直接搜索复杂度是O(3^n)，过不了。
使用折半搜索，对于前半部分搜索得出结果，设搜出来的和为s，使用
map或者哈希在对应的位置存下结果，然后搜索后半部分，加上对应位置的结果。但是这样会有重复算的情况，因为两种情况不同只取决于取出来的人而不是怎么分队。所以我们在搜索前半段时要用一个二进制数保存下所选人的情况，然后去重一下即可。
复杂度为前半部分+后半部分，也就是O(3^{\frac{n}{2}}+3^{\frac{n}{2}})=O(3^{\frac{n}{2}})。
是可以在时限内通过的。
例题2
JZOJ 5797
JZOJ 5797
还是直接折半搜索，搜出前半部分后，我们需要记录下最后一个楼房的高度h1和楼房的金币之和s1。
在后半部分搜索出来一个结果之后，我们需要记录跳的第一个楼房高度h2和金币之和s2，然后根据条件，必须满足：
h1≤h2
s1+s2≥k
也就是
s1≥k-s2
因此我们可以设f[i][j]表示前半部分的结果中满足h1≤i和s1≥j的情况有多少。由于数据很大没法直接存，因此需要离散化，离散化之后这个数组需要的空间是O(\frac{n}{2}2^{\frac{n}{2}})，由于出题人成心卡内存还是存不下，于是就需要把前半部分少搜一个，后半部分多搜一个，这样空间极限复杂度是O(19*2^{19})，时间极限复杂度是O(2^{21})，可以在时限内通过。
Code：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long ll;
int lenh, arrh[23], leng;
ll ans, k, g[43], gsum[(1 << 19) + 3];
int n, mid, h[43];
int buc[23][(1 << 19) + 3];
void dfs1(int now, ll sum, int las)
{
if (now > mid) { gsum[++leng] = sum; return; }
if (h[now] >= h[las]) dfs1(now + 1, sum + g[now], now);
dfs1(now + 1, sum, las);
}
void dfs2(int now, ll sum, int las)
{
if (now > mid)
{
buc[h[las]][lower_bound(gsum + 1, gsum + leng + 1, sum) - gsum]++;
return;
}
if (h[now] >= h[las]) dfs2(now + 1, sum + g[now], now);
dfs2(now + 1, sum, las);
}
void dfs3(int now, ll sum, int las, int fir)
{
if (now > n)
{
if (fir) ans += buc[upper_bound(arrh + 1, arrh + lenh + 1, h[fir]) - arrh - 1][lower_bound(gsum + 1, gsum + leng + 1, k - sum) - gsum];
else ans += buc[lenh][lower_bound(gsum + 1, gsum + leng + 1, k - sum) - gsum];
return;
}
if (h[now] >= h[las])
{
if (!fir) dfs3(now + 1, sum + g[now], now, now);
else dfs3(now + 1, sum + g[now], now, fir);
}
dfs3(now + 1, sum, las, fir);
}
int main()
{
freopen("san.in", "r", stdin);
freopen("san.out", "w", stdout);
scanf("%d%lld", &n, &k);
for (int i = 1; i <= n; i++) scanf("%d%lld", h + i, g + i);
mid = n / 2 - 1; //前半部分少搜一个
if (mid < 1) mid = 1;
for (int i = 1; i <= mid; i++) arrh[++lenh] = h[i];
sort(arrh + 1, arrh + lenh + 1);
lenh = unique(arrh + 1, arrh + lenh + 1) - arrh - 1;
for (int i = 1; i <= mid; i++) h[i] = lower_bound(arrh + 1, arrh + lenh + 1, h[i]) - arrh;
dfs1(1, 0, 0);
sort(gsum + 1, gsum + leng + 1);
leng = unique(gsum + 1, gsum + leng + 1) - gsum - 1;
dfs2(1, 0, 0);
for (int i = 1; i <= lenh; i++)
for (int j = leng; j >= 1; j--)
buc[i][j] += buc[i - 1][j] + buc[i][j + 1] - buc[i - 1][j + 1]; //用类似二位前缀和的方法计算f
dfs3(mid + 1, 0, 0, 0);
printf("%lld\n", ans);
fclose(stdin);
fclose(stdout);
return 0;
}
总结
很多看似DP，或者看上去很劝退的题目，其实要仔细观察数据范围，万一真的是暴力呢？如果一般暴力不行就优化，用各种方法优化，常数和复杂度都优化，这应该就是搜索题的应付方法了。
