首页 > 代码库 > 光棍组织
光棍组织
MM 虽然一辈子只要一个，但是也得早点解决。于是，n 个光棍们自发组成了一个光棍组织
（ruffian organization，By Wind 乱译）。现在，光棍们打算分成几个小组，并且分头为 找 MM 事业做贡献（For example：searching，hunting……By Wind 乱译）。
对于这 n 个光棍的任意一个组合，都有一个被称为“和谐度”的东西，现在，他们想知道， 如何分组可以使和谐度总和最大。
每个光棍都必须属于某个分组，可以一个人一组。
这应该是一个很经典的问题了，不像01背包每个物品只有放或不放两个决策，不像普通的连续的分组dp只有放前面的组和自己再创一个组两个决策；
这个问题的物品是可以放在任意一个组里的，这就对后面的决策有了后效性；
但如果纯粹的dfs，按照阶乘的复杂度，很容易爆掉；
我之后的思路是分治，就是枚举当前这个集合的所有组合，然后找到与之对应的互补的组合，两边分别dfs+记忆化搜索；
发现好难实现啊，网上找到了标程，转化成了c++版本，好厉害啊，orz；
附标程：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<cstdlib> 6 #include<ctime> 7 #include<vector> 8 #include<algorithm> 9 #include<queue>10 #include<map>11 using namespace std;12 #define LL long long13 int n;14 int a[70000],f[70000];15 int b[17];16 string g(int x){17 string s="";18 while(x){19 if(x%2)s=‘1‘+s;20 x/=2;21 }22 return s;23 }24 int dfs(int i){25 if(i==0)return 0;26 if(f[i]>0)return f[i];27 int x,y,z,tn;28 x=i&(-i);29 y=i&(~x);30 z=0;31 do{32 tn=dfs(y-z)+a[x|z];33 if(tn>f[i])f[i]=tn;34 z=((z|(~y))+1)&y;35 }while(z);36 return f[i];37 }38 int main(){39 freopen("1.in","r",stdin);40 freopen("1.out","w",stdout);41 scanf("%d",&n);42 for(int i=1;i<=(1<<n)-1;i++)scanf("%d",&a[i]);43 printf("%d",dfs((1<<n)-1));44 }
付个人理解：
以往的枚举2进制的所有组合都是用+1的手法来做的，这个标程也不例外；
i的二进制一般是这10100...101010010（类似）；
((z|(~y))+1)&y实现了仅在原来i的二进制中是1的点的进位；
很好很强大；学习了；
光棍组织
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。