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 long
13 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 }
View Code
附个人理解:
以往的枚举2进制的所有组合都是用+1的手法来做的,这个标程也不例外;
i的二进制一般是这10100...101010010(类似);
((z|(~y))+1)&y实现了仅在原来i的二进制中是1的点的进位;
很好很强大;学习了;
原文链接: https://www.cnblogs.com/chadinblog/p/5882605.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/240671
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!