uva 11088 暴力枚举子集/状压dp

对于每一种子集的情况暴力枚举最后一个三人小组取最大的一种情况即可，我提前把三个人的子集情况给筛出来了。即 f[S]=MAX{ f[S^X]+ok(X) | X€三个人的子集 } ok(X)判断X所有的和是否>=20;

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #include<vector>
 6 #include<stack>
 7 using namespace std;
 8 #define inf 0x3f3f3f3f
 9 int f[(1<<15)+15];
10 vector<int>thr;
11 int total(int x)
12 {
13     int s=0;
14     while(x){
15         if(x&1) s++;
16         x>>=1;
17     }
18     return s;
19 }
20 void init()
21 {
22     int all=(1<<15);
23     for(int i=0;i<all;++i)
24         if(total(i)==3) thr.push_back(i);
25 }
26 int a[20];
27 bool can(int x)
28 {
29     int s=0;
30     for(int j=0;j<15;++j)
31         if(x&(1<<j)) s+=a[j+1];
32     return s>=20;
33 }
34 int main()
35 {
36     int N=1,M,i,j,k=0,t;
37     init();
38     while(cin>>N&&N){
39         for(i=1;i<=N;++i) cin>>a[i];
40         memset(f,0,sizeof(f));
41         int all=(1<<N);
42         for(i=0;i<all;++i)
43         {
44             for(j=0;j<thr.size()&&i>=thr[j];++j)
45             {
46                 if((i&thr[j])==thr[j]){
47                     f[i]=max(f[i],f[i^thr[j]]+can(thr[j]));
48                 }
49             }
50         }
51         printf("Case %d: %d
",++k,f[all-1]);
52     }
53     return 0;
54 }