HDU 4277 USACO ORZ [状态压缩+枚举]

　　很黄很暴力的枚举，加上了状态压缩的优化。

　　用15位的状态压缩木棍，1代表使用，0代表没有使用。然后枚举1~2^15作为一根木棍的组成，取反后的状态为令两根木棍，再枚举这个状态的所有子集，即将它拆成两根木棍。。。然后HASH一下就可以了。

　　其实是有重复状态的，每种状态都会重复六次。加上一个优化if(len[i]>=len[ii])continue;当第一条边比剩余两条边的和都大的时候就不去枚举剩余两条边的组合，这样效率会高上很多。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 #include <set>
 5 #define MOD 100007
 6 #define MAXD 10000010
 7 int cas,n,x,len[1<<15],hash;
 8 int first[MOD],next[MAXD],es;
 9 int numa[MAXD],numb[MAXD],size;
10 void ins(int x,int y,int p){
11     numa[es]=x,numb[es]=y,next[es]=first[p],first[p]=es++;
12 }
13 bool findhash(int x,int y){
14     int p=(x*10000+y)%MOD;
15     for(int i=first[p];i!=-1;i=next[i])if(numa[i]==x&&numb[i]==y)return 1;
16     return 0;
17 }
18 void inshash(int x,int y){
19     if(!findhash(x,y)){
20         size++;//哈希表的大小
21         int p=(x*10000+y)%MOD;
22         ins(x,y,p);
23     }
24 }
25 int main(){
26     //freopen("test.in","r",stdin);
27     for(scanf("%d",&cas);cas--;){
28         scanf("%d",&n);
29         memset(first,-1,sizeof first);es=size=0;
30         int full=1<<n,ans=0;
31         memset(len,0,sizeof len);
32         for(int i=0;i<n;i++)scanf("%d",&len[1<<i]);
33         for(int i=0;i<full;i++)len[i]=len[(i-1)&i]+len[i&-i];
34         for(int i=1;i<full;i++){
35             int ii=~i&(full-1);
36             //剪枝,如果第一条边大于后两条边之和就不用加了
37             if(len[i]>=len[ii])continue;
38             for(int j=(ii-1)&ii;j;j=(j-1)&ii){
39                 int k=ii-j;
40                 
41                 if(len[i]>=len[j]&&len[j]>=len[k])inshash(len[i],len[j]);
42             }
43         }
44         printf("%d\n",size);
45 
46     }
47     return 0;
48 }