题目

Description

　　D(1<=D<=15)种病毒正袭击着牧场里的奶牛，这给牧场主约翰造成了极大的麻烦，因为按照卫生检疫条例的规定：如果牛奶中的病毒超过K(1<=K<=D)种则不允许被销售，约翰的牧场里共有N(1<=N<=1,000)头奶牛，每头奶牛都带有若干种病毒，约翰挤出的牛奶是混放在一起的，要求约翰最多可以挤多少头奶牛的牛奶，使得混放在一起的牛奶不包含超过K种的病毒。

 

Input

　　输入文件的第一行有三个用空格隔开的整数N,D,K，接下来的N行每行表示一头奶牛的病毒列表，每行的第一个数d_i(0<=d_i<=D)表示该头奶牛共携带了d_i种病毒，紧接着的d_i个整数表示该头奶牛共携带的每一种病毒的编号，相邻两数之间用空格隔开。

Output

　　输出文件仅有一行包含一个整数，表示约翰最多可以挤多少头奶牛的牛奶，使得混放在一起的牛奶不包含超过K种的病毒。

 

Sample Input

6 3 201 11 21 32 2 12 2 1

Sample Output

5

 

Data Constraint

 

 

Hint

【样例说明】

　　约翰可以挤编号为1,2,3,5,6的奶牛的牛奶，牛奶中只含两种病毒(#1和#2)，病毒种数不大于K(2)。

分析

• 状压一下快一点

代码

1 #include
     
       2 #include
      
        3 using namespace std; 4 long long v[1010]; 5 long long f[1010]; 6 int t[500000]; 7 void take(int n)     8 { 9      for (int i=0;i<=(1<
       
        >n>>d>>k;23     for (int i=1,x;i<=n;i++)24     {25         cin>>x;26         for (int j=1,a;j<=x;j++)27         {28             cin>>a;29             v[i]=v[i]|(1<<(a-1));30         }31     }32     take(d);33     int sum,ans=-10000;34     for (int i=0;i<=(1<
        
         k) continue;38         for (int j=1;j<=n;j++)39         {40             if ((v[j]&i)==v[j])41               sum++;42         }43         ans=max(ans,sum);44     }45     cout<