当前位置：首页 > news >正文

P1382 光棍组织

news 来源：原创 2024/5/6 1:38:20

我现在TMD连dfs都不会写了

原题：

MM 虽然一辈子只要一个，但是也得早点解决。于是，n 个光棍们自发组成了一个光棍组织
（ruffian organization，By Wind 乱译）。现在，光棍们打算分成几个小组，并且分头为找 MM 事业做贡献（For example：searching，hunting……By Wind 乱译）。
对于这 n 个光棍的任意一个组合，都有一个被称为“和谐度”的东西，现在，他们想知道，如何分组可以使和谐度总和最大。
每个光棍都必须属于某个分组，可以一个人一组。

n<=16

恩，把个中分组的方案和价值都直接给了，然后让选择的方案全部&起来等于(1<<n)-1（当然不能有冲突），DP想不到方法，n<=16似乎可以搜索

最开始做的时候是bfs，每次从1到(1<<n)-1找不冲突的方案，这样会T得很惨（至少要((1<<n)-1)^2）

然后容易想到是因为遍历1到(1<<n)-1过程中无效的枚举太多，所以可以直接dfs有效的状态

然后dfs傻逼了写了两天

原来写的：for(int i=z;i<n;i++)if(y&power2[i]) dfs(x,y-power2[i],i+1),dfs(x,y,i+1);

实际上应该是酱紫：if(y&power2[z])dfs(x,y-power2[z],z+1); dfs(x,y,z+1);

原来的内种写法会有非常多的重复

在发现dfs有问题之前一直在怀疑是用了不正确的写法，参考了chad的题解又写了个分治（反向dfs）的，然后才发现dfs制杖了（分治的应该也对了）

经实测，bfs的时候搞一个spfa中的visited来表示这个元素是否在队中，如果在队中就不进队，这个优化效果还是不错的

尝试反向可以是突破点，比如反向搜索，反向枚举，甚至反向DP

代码（分治的丢了）：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 using namespace std;
 7 int read(){int z=0,mark=1;  char ch=getchar();
 8     while(ch<'0'||ch>'9'){if(ch=='-')mark=-1;  ch=getchar();}
 9     while(ch>='0'&&ch<='9'){z=(z<<3)+(z<<1)+ch-'0';  ch=getchar();}
10     return z*mark;}
11 int n,a[110000];  int power_top;
12 long long f[110000];
13 int dui[11000000],tou=0;  bool visited[110000];
14 int power2[20];  void get_power2(){power2[0]=1;for(int i=1;i<=16;i++)power2[i]=power2[i-1]<<1;}
15 void dfs(int x,int y,int z){
16     if(z==n){
17         if(f[x|y]<f[x]+a[y]){  f[x|y]=f[x]+a[y];
18         if(!visited[x|y])  dui[++tou]=x|y,visited[x|y]=true;}
19         return ;}
20     if(y&power2[z])dfs(x,y-power2[z],z+1);  dfs(x,y,z+1);}
21 void bfs(){
22     memset(visited,0,sizeof(visited));
23     dui[tou=1]=0;  f[0]=0;  visited[0]=true;
24     for(int k=1;k<=tou;k++)  dfs(dui[k],power_top^dui[k],0),visited[dui[k]]=false;}
25 int main(){//freopen("ddd.in","r",stdin);
26     memset(f,-10,sizeof(f));
27     get_power2();
28     cin>>n;  power_top=(1<<n)-1;
29     for(int i=1;i<=power_top;i++)  a[i]=read();
30     bfs();
31     cout<<f[power_top]<<endl;
32     //cout<<tou<<endl;
33     return 0;
34 }