「bzoj2679」「USACO 2012 Open Gold」Balanced Cow Subsets - meet-in-the-middle

题目大意

    从$N$个数(数的范围$1\sim100,000,000)$，选出其中$K$个数作为一个集合，该集合$K$个数能分成左右相等的和。问有多少种集合方案？

---

题目分析

普通的搜索时间复杂度为$O(3^n)$。
考虑每个数是分为左边集合$+$，右边集合$-$，不选$0$三种方案。

考虑使用meet-in-the-middle优化时间。
先搜索前半部分，使用vector将对应集合划分的权值和，再搜索后半部分，记录下来每个集合划分和权值和。

对后半部分排序，使用双指针统计相同的权值和，添加标记累加答案。

时间复杂度$O(2\cdot3^{10}+2^{10}3^{10})$。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=25,maxs=1100005,mids=60005;

struct Node {
	int sum,S;
	Node(int a=0,int b=0):sum(a),S(b) {}
	bool operator < (const Node& b) const {
		return sum<b.sum;
	}
};

vector<int> f[mids];
vector<Node> g;
int n,mid,a[maxn];
bool vst[maxs];

void Dfsl(int Now,int sum,int S) {
	if(Now>mid) {
		f[S].push_back(sum);
		return;
	}
	Dfsl(Now+1,sum,S);
	Dfsl(Now+1,sum-a[Now],S|(1<<(Now-1)));
	Dfsl(Now+1,sum+a[Now],S|(1<<(Now-1)));
}

void Dfsr(int Now,int sum,int S) {
	if(Now>n) {
		g.push_back(Node(sum,S));
		return;
	}
	Dfsr(Now+1,sum,S);
	Dfsr(Now+1,sum-a[Now],S|(1<<(Now-1)));
	Dfsr(Now+1,sum+a[Now],S|(1<<(Now-1)));
}

int main() {
	n=Get_Int();
	mid=n>>1;
	for(int i=1; i<=n; i++)a[i]=Get_Int();
	Dfsl(1,0,0);
	Dfsr(mid+1,0,0);
	sort(g.begin(),g.end());
	for(int S=0; S<(1<<mid); S++) {
		sort(f[S].begin(),f[S].end());
		auto it=f[S].begin();
		for(auto x:g) {
			while(it!=f[S].end()&&*it<x.sum)it++;
			if(it==f[S].end())break;
			if(*it==x.sum)vst[S|x.S]=1;
		}
	}
	int ans=0;
	for(int i=1; i<(1<<n); i++)ans+=vst[i];
	printf("%d\n",ans);
	return 0;
}