[Usaco2012 Open]Balanced Cow Subsets

搜索 meet_in_the_middle

题面

给$n$个数，从中任意选出一些数，使这些数能分成和相等的两组。
求有多少种选数的方案。

• $n\leq20$

解析

暴力应该是$O(3^n)$的。
一般来说，$n\leq40$以内的搜索题目，用$meet\ in\ the\ middle$准没错。
于是存下前$n/2$个数的$3^{10}$种方案，再搜后面$n/2$个数的方案并与前面匹配即可。

蒟蒻为什么会$GG$呢？因为它没想到可以维护这两组间的差值。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;++i)
#define fq(i,a,b) for(re int i=a;i>=b;--i)
using namespace std;
const int N=1e6+1e5;
int n,a[30],m,ok[N],ans;
map<int,int>M;
set<int>S[60000];
set<int>::iterator it;
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!=-'-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void dfs(re int x,re int tot,re int s)
{
  if(x>n/2)
    {
      if(M.find(tot)==M.end()) M[tot]=++m;
      re int t=M[tot];
      S[t].insert(s);
      return;
    }
  dfs(x+1,tot,s);
  dfs(x+1,tot+a[x],s|(1<<x-1));
  dfs(x+1,tot-a[x],s|(1<<x-1));
}
il void DFS(re int x,re int tot,re int s)
{
  if(x>n)
    {
      if(M.find(tot)==M.end()) return;
      re int t=M[tot];
      for(it=S[t].begin();it!=S[t].end();++it)
    ok[(*it)|s]=1;
      return;
    }
  DFS(x+1,tot,s);
  DFS(x+1,tot+a[x],s|(1<<x-1));
  DFS(x+1,tot-a[x],s|(1<<x-1));
}
int main()
{
  n=gi();
  fp(i,1,n) a[i]=gi();
  dfs(1,0,0);DFS(n/2+1,0,0);
  fp(i,1,(1<<n)-1) ans+=ok[i];
  printf("%d\n",ans);
  return 0;
}