折半搜索 学习笔记

1.概述

折半搜索，又称meet in the middle，通常是把不能直接做的题目分成两半。

把这两半分别搜索。

比如$O(2^n)$的做法，有时可以分解为$O(2*2^{\frac n 2})$，但是要考虑合并的复杂度。

合并时可以通过排序，使一部分有序，再通过二分或其他做法合并答案。

其实折半状压也是运用类似的思想。

可以解决一些统计方案，但爆搜会T的题目

2.例题

P4799 [CEOI2015 Day2]世界冰球锦标赛

Bobek有M元钱，共有N场比赛，每场比赛的门票都有一个价格 。
问在总票价不超过M元钱的情况下，Bobek共有多少种不同的观赛方案。
注1：若方案1中观看了某场比赛，方案2中未观看该场，则认为两种方案不同。
注2： 。

折半搜索模板。

只需要拆成两部分，二分查找合适的就行。

注意相等的可以取，所以要用upper_bound查找，数量减一。

但因为vector的下标从0开始，所以就不用了。

Code：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define int long long
vector<int> a, b;
int n, m, A[59], ans;
inline void dfs(int l, int r, int sum, bool sign)
{
	if (sum > m)
		return;
	if (l > r)
	{
		if (!sign)
			a.push_back(sum);
		else
			b.push_back(sum);
		return;
	}
	dfs(l + 1, r, sum + A[l], sign);
	dfs(l + 1, r, sum, sign);
}

signed main()
{
	scanf("%lld%lld", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%lld", &A[i]);
	dfs(1, n / 2, 0, 0);
	dfs(n / 2 + 1, n, 0, 1);
	sort(a.begin(), a.end());
	for (int i = 0; i < b.size(); i++)
		ans += upper_bound(a.begin(), a.end(), m - b[i]) - a.begin();
	printf("%lld", ans);
	return 0;
}