P3067【Balanced Cow Subsets G】

· · 题解

首先，一个有20头奶牛，那么考虑对于每一头奶牛来说有3种状态，放在一组，放在另一组，不放任何一组，如果暴力枚举时间复杂度为O(3^n)>1E9，无法接受。

考虑将n头奶牛分为两半，每组分别暴力求解，时间复杂度O(3^\frac{n}{2})可以通过。

假设在前一半中，在第一组中放的数的和为a，在第二组中放的数为b。

假设在后一半中，在第一组中放的数的和为c，在第二组中放的数为d。

那么a+c=b+d

由于我们要对每一半分开处理，所以考虑将同一半的数放在一起处理，即移项得a-b=c-d。

因此，我们只需要统计在每一半中和为a-b的方案有多少中，在进行组合。

一个数被放入第一组中，a-b的值变大，在第二组中，a-b的值变小，如果不放，则a-b不变，所以维护a-b的值即可。

#include<bits/stdc++.h>
using namespace std;
int n,N,a[21],ans[2000001],s,tot;
vector<int> p[2000001];
map<int,int> b;
void dfs1(int x,int sum,int now){//对前一半搜索，x表示到了第几个，sum表示a-b的值，now表示状压，取了那些数
    if(x>N){
        if(b[sum]==0) b[sum]=++tot;//离散化
        p[b[sum]].push_back(now);//放入方案
        return;
    }
    dfs1(x+1,sum+a[x],now|(1<<(x-1)));  //三种情况讨论
    dfs1(x+1,sum-a[x],now|(1<<(x-1)));  
    dfs1(x+1,sum,now);
} 
void dfs2(int x,int sum,int now){//对后一半搜索，同上
    if(x>n){ 
        int t=b[sum];
        if(t!=0)  for(int i=0;i<p[t].size();i++)  ans[p[t][i]|now]=1;//对于每一种可能的组合，将值赋为1，注意，题目中要求的方案数为取数的方案数而不是分数的方案数，因此不是+1而是=1
        return;
    }
    dfs2(x+1,sum+a[x],now|(1<<(x-1)));  
    dfs2(x+1,sum-a[x],now|(1<<(x-1)));  
    dfs2(x+1,sum,now);
} 
int main(){
    scanf("%d",&n); N=n/2;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    dfs1(1,0,0);
    dfs2(N+1,0,0);
    for(int i=1;i<=(1<<n);i++)s+=ans[i];
    printf("%d",s);
}