USACO12OPEN Balanced Cow Subsets G（meet in the middle）
洛谷P3067 [USACO12OPEN] Balanced Cow Subsets G
题目大意
我们定义一个奶牛集合 S S S是平衡的，当且仅当满足以下两个条件：
- S S S非空
- S S S可以被划分为两个集合 A , B A,B A,B，满足 A A A里的奶牛产量之和等于 B B B里的牛奶产量之和
现在给定大小为 n n n的奶牛集合 S S S，询问它有多少个子集是平衡的。
1 ≤ n ≤ 20 , 1 ≤ a i ≤ 1 0 8 1\leq n\leq 20,1\leq a_i\leq 10^8 1≤n≤20,1≤ai≤108
题解
前置知识：折半搜索（meet in the middle）
我们考虑枚举 S S S的子集 S ′ S' S′，在枚举子集 S ′ S' S′中的每个子集来判断 S ′ S' S′是否平衡。每个奶牛有三种情况：不在 S S S中，在 S S S中但不在 S ′ S' S′中，在 S S S中且在 S ′ S' S′中。如果枚举每种情况的话，时间时间复杂度是 O ( 3 n ) O(3^n) O(3n)的，我们考虑优化。
我们可以用折半搜索，将所有奶牛分为两个部分。
设前一部分中划分到集合 A A A的元素的值之和为 a a a，划分到集合 B B B的元素的值之和为 b b b。
设后一部分中划分到集合 A A A的元素的值之和为 c c c，划分到集合 B B B的元素的值之和为 d d d。
那么， a + c = b + d a+c=b+d a+c=b+d，移项的 a − b = c − d a-b=c-d a−b=c−d。
我们先处理出前一部分的 a − b a-b a−b，然后对于每一个 c − d c-d c−d，在前面处理出的 a − b a-b a−b中查找与 c − d c-d c−d相等的并判断这两部分构成的集合是否是平衡的，是的话就更新答案即可。
处理前一部分和后一部分的时间复杂度都为 O ( 3 n / 2 ) O(3^{n/2}) O(3n/2)，合并的时间复杂度为 O ( n 3 n ) O(n3^n) O(n3n)，所以总时间复杂度为 O ( n 3 n ) O(n3^n) O(n3n)。
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;
}