USACO12OPEN Balanced Cow Subsets G（meet in the middle）

这篇具有很好参考价值的文章主要介绍了USACO12OPEN Balanced Cow Subsets G（meet in the middle）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

洛谷P3067 [USACO12OPEN] Balanced Cow Subsets G

题目大意

我们定义一个奶牛集合 $S$ 是平衡的，当且仅当满足以下两个条件：

$S$ 非空
$S$ 可以被划分为两个集合 $A, B$ ，满足 $A$ 里的奶牛产量之和等于 $B$ 里的牛奶产量之和

现在给定大小为 $n$ 的奶牛集合 $S$ ，询问它有多少个子集是平衡的。

$1\leq n\leq 20,1\leq a_i\leq 10^8$

题解

前置知识：折半搜索（meet in the middle）

我们考虑枚举 $S$ 的子集 $S^{'}$ ，在枚举子集 $S^{'}$ 中的每个子集来判断 $S^{'}$ 是否平衡。每个奶牛有三种情况：不在 $S$ 中，在 $S$ 中但不在 $S^{'}$ 中，在 $S$ 中且在 $S^{'}$ 中。如果枚举每种情况的话，时间时间复杂度是 $O(3^n)$ 的，我们考虑优化。

我们可以用折半搜索，将所有奶牛分为两个部分。

设前一部分中划分到集合 $A$ 的元素的值之和为 $a$ ，划分到集合 $B$ 的元素的值之和为 $b$ 。

设后一部分中划分到集合 $A$ 的元素的值之和为 $c$ ，划分到集合 $B$ 的元素的值之和为 $d$ 。

那么， $a + c = b + d$ ，移项的 $a - b = c - d$ 。

我们先处理出前一部分的 $a - b$ ，然后对于每一个 $c - d$ ，在前面处理出的 $a - b$ 中查找与 $c - d$ 相等的并判断这两部分构成的集合是否是平衡的，是的话就更新答案即可。

处理前一部分和后一部分的时间复杂度都为 $O(3^{n/2})$ ，合并的时间复杂度为 $O(n3^n)$ ，所以总时间复杂度为 $O(n3^n)$ 。文章来源地址https://www.toymoban.com/news/detail-717079.html

code

#include<bits/stdc++.h>
using namespace std;
int n,cnt=0,ans=0,a[25],z[1<<20];
map<int,int>mp;
vector<int>v[1<<20];
void dfs1(int t,int sum,int now){
	if(t==n/2+1){
		if(!mp[sum]) mp[sum]=++cnt;
		v[mp[sum]].push_back(now);
		return;
	}
	dfs1(t+1,sum+a[t],now|(1<<t-1));
	dfs1(t+1,sum-a[t],now|(1<<t-1));
	dfs1(t+1,sum,now);
}
void dfs2(int t,int sum,int now){
	if(t==n+1){
		int tmp=mp[sum];
		if(tmp)
		for(int i=0;i<v[tmp].size();i++){
			z[v[tmp][i]|now]=1;
		}
		return;
	}
	dfs2(t+1,sum+a[t],now|(1<<t-1));
	dfs2(t+1,sum-a[t],now|(1<<t-1));
	dfs2(t+1,sum,now);
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	dfs1(1,0,0);
	dfs2(n/2+1,0,0);
	for(int i=1;i<1<<n;i++) ans+=z[i];
	printf("%d",ans);
	return 0;
}