海原县住房和城乡建设局网站,三合一网站方案,网站卡密怎么做,php网站后台管理系统洛谷P3067 [USACO12OPEN] Balanced Cow Subsets G
题目大意
我们定义一个奶牛集合 S S S是平衡的#xff0c;当且仅当满足以下两个条件#xff1a; S S S非空 S S S可以被划分为两个集合 A , B A,B A,B#xff0c;满足 A A A里的奶牛产量之和等于 B B B里的牛奶产量之和
…洛谷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 acbd acbd移项的 a − b c − d a-bc-d a−bc−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
#includebits/stdc.h
using namespace std;
int n,cnt0,ans0,a[25],z[120];
mapint,intmp;
vectorintv[120];
void dfs1(int t,int sum,int now){if(tn/21){if(!mp[sum]) mp[sum]cnt;v[mp[sum]].push_back(now);return;}dfs1(t1,suma[t],now|(1t-1));dfs1(t1,sum-a[t],now|(1t-1));dfs1(t1,sum,now);
}
void dfs2(int t,int sum,int now){if(tn1){int tmpmp[sum];if(tmp)for(int i0;iv[tmp].size();i){z[v[tmp][i]|now]1;}return;}dfs2(t1,suma[t],now|(1t-1));dfs2(t1,sum-a[t],now|(1t-1));dfs2(t1,sum,now);
}
int main()
{scanf(%d,n);for(int i1;in;i){scanf(%d,a[i]);}dfs1(1,0,0);dfs2(n/21,0,0);for(int i1;i1n;i) ansz[i];printf(%d,ans);return 0;
}
