POJ 2453

  1 #include <iostream>
  2 #include <algorithm>
  3 #include <cmath>
  4 #define MAXN 1000
  5 #define M_15 15
  6 using namespace std;
  7 
  8 int _b[M_15];
  9 struct node
 10 {
 11     int tot;
 12     int v;
 13     int d[15];
 14     node()
 15     {
 16         v = 0;
 17         tot = 0;
 18     }
 19 };
 20 
 21 void fun_3();
 22 node _[MAXN];
 23 int fun_2(int sum);
 24 int fun_1(int d,int k);
 25 int n;
 26 int d;
 27 int main()
 28 {
 29     //freopen("acm.acm","r",stdin);
 30 
 31     int k;
 32     int i;
 33     int j;
 34     int p;
 35     int tem;
 36     cin>>n;
 37     cin>>d;
 38     cin>>k;
 39 
 40     for(i = 0; i < n; ++ i)
 41     {
 42         cin>>_[i].tot;
 43         for(j = 0; j < _[i].tot; ++ j)
 44         {
 45             //cin>>_[i].d[j];
 46             cin>>tem;
 47             _[i].d[tem-1] = 1;
 48         }
 49     }
 50     fun_3();
 51     cout<<fun_1(d,k)<<endl;
 52 }
 53 
 54 int fun_1(int d,int k)
 55 {
 56     int i;
 57     int j;
 58     int sum;
 59     int max = -1;
 60     for(i = 0; i < k; ++ i)
 61     {
 62         _b[i] = 1;
 63     }
 64     sort(_b,_b+d);
 65     sum = 0;
 66     int tem = 0;
 67     for(i = d-1; i >= 0; -- i)
 68     {
 69         sum += _b[i]*pow((double)2,tem);
 70         ++ tem;
 71     }
 72 //    cout<<sum<<endl;
 73     if((tem = fun_2(sum) ) > max)
 74     {
 75         max = tem;
 76     }
 77 //    cout<<tem<<endl;
 78     while(next_permutation(_b,_b+d))
 79     {
 80         sum = 0;
 81         int tem = 0;
 82         for(i = d-1; i >= 0; -- i)
 83         {
 84             sum += _b[i]*pow((double)2,tem);
 85             ++ tem;
 86         }
 87 //        cout<<sum<<endl;
 88         tem = fun_2(sum);
 89 //        cout<<tem<<endl;
 90         if(tem > max)
 91         {
 92             max = tem;
 93         }
 94     }
 95     return max;
 96     
 97 }
 98 
 99 int fun_2(int sum)
100 {
101     int i;
102     int j;
103     int t = 0;
104     for(i = 0; i < n; ++ i)
105     {
106         if(sum == (sum|_[i].v) )
107         {
108             ++ t;
109         }
110     //    cout<<sum<<"_"<<_[i].v<<endl;
111     }
112 //    cout<<"000000000000000000000————————"<<t<<endl;
113     return t;
114 }
115 
116 void fun_3()
117 {
118     int tem = 0;
119     int i;
120     int j;
121     for(i = 0; i < n; ++ i)
122     {
123         tem = 0;
124         for(j = d-1; j >= 0; -- j)
125         {
126             _[i].v += _[i].d[j]*pow((double)2,tem);
127             ++ tem;
128         }
129     //    cout<<_[i].v<<endl;
130     //    cout<<" d "<<d<<endl;
131     }
132 }