自动搬运

查看原文

来自洛谷，原作者为

	houzhiyuan 花谢花飞花满天，红消香断有谁怜？

搬运于2025-08-24 21:44:57，当前版本为作者最后更新于2021-03-01 18:26:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先，一个有$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);
}