洛谷P3067/USACO12OPEN 平衡的奶牛群Balanced Cow Subsets

@Pelom  October 24, 2019

题意

给出$n$个数,从中选出一些,求选出的数能分成相等的两份的方案数

数据范围:$2 \le n \le 20$

题解

对于每个元素,无非$3$种状态:

  • $0$ 不选
  • $-1$ 左
  • $1$ 右

但直接搜索复杂度达到$O(3^n)$
考虑折半搜索
将组合二进制压缩,前半搜索记录下可能的$sum$,后半搜索从前半中找到相等的$sum$(其实是找$-sum$,但是是等价的),则此种选择方案成立
由于$sum$较大,需要离散化(不必排序)

注: 由于map常数较大,可以开启O2优化或考虑使用排序或unordered_map

代码:

#include<iostream>
#include<cstdio>
#include<map>
#include<vector>
using namespace std;
const int N=20;
int n,tot,cnt,ans;
int a[N+1];
map<int,int> M;
vector<int> s[(1<<N)+1];
bool vis[(1<<N)+1];
void dfs1(int x,int sum,int stt){
    if(x>=tot){
        if(!M.count(sum))
            M[sum]=++cnt;
        s[M[sum]].push_back(stt);
        return ;
    }
    dfs1(x+1,sum,stt);
    dfs1(x+1,sum-a[x],stt|(1<<x));
    dfs1(x+1,sum+a[x],stt|(1<<x));
}
void dfs2(int x,int sum,int stt){
    if(x>=n){
        if(M.count(sum)){
            int t=M[sum];
            for(int i=0;i<s[t].size();i++)
                vis[s[t][i]|stt]=1;
        }
        return ;
    }
    dfs2(x+1,sum,stt);
    dfs2(x+1,sum-a[x],stt|(1<<x));
    dfs2(x+1,sum+a[x],stt|(1<<x));
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    tot=n>>1;
    dfs1(0,0,0);
    dfs2(tot,0,0);
    tot=1<<n;
    for(int i=1;i<tot;i++)
        ans+=vis[i];
    printf("%d",ans);
    return 0;
}

添加新评论