Description
Input
Output
Sample Input
6 3 2 0 1 1 1 2 1 3 2 2 1 2 2 1
Sample Output
5
思路：需要用到位运算，D最为16,用一个int数（32位 > 16位，足够表示）的每个二进制位表示病毒的存在与否，1为存在，0不存在，这样复杂度为2^16*n(通过剪枝实际达不到这么大)，可以接受。因此有两种方法解本题，（1），dfs,枚举D的k-组合。（2），通过二进制枚举D的k-组合。
用dfs，最后程序跑得时间是32ms，二进制枚举跑得时间是285ms，如此大的差距，原因就是二进制把所有组合都枚举完了，其中包含很多冗余状态，说白了就是大爆力。
DFS版：（32ms）
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<cmath> 5 #include<string> 6 #include<algorithm> 7 #define MAXN 1111 8 using namespace std; 9 int cow[MAXN],vis[MAXN],N,D,K,ans; 10 void dfs(int idx,int cnt,int sum){ 11 if(cnt == K){ 12 int num = 0; 13 for(int i = 0;i < N;i ++) 14 if(cow[i] == (cow[i] & sum)) num++; 15 ans = max(ans,num); 16 return; 17 } 18 for(int i = idx;i < D;i ++){ 19 if(!vis[i]){ 20 vis[i] = 1; 21 dfs(i+1,cnt+1,sum|(1 << i)); 22 vis[i] = 0; 23 } 24 } 25 } 26 int main(){ 27 int tmp,kind; 28 // freopen("in.c","r",stdin); 29 while(~scanf("%d%d%d",&N,&D,&K)){ 30 memset(cow,0,sizeof(cow)); 31 memset(vis,0,sizeof(vis)); 32 for(int i = 0;i < N;i ++){ 33 scanf("%d",&tmp); 34 for(int j = 0;j < tmp;j ++){ 35 scanf("%d",&kind); 36 cow[i] |= (1 << (kind-1)); 37 } 38 } 39 ans = 0; 40 dfs(0,0,0); 41 printf("%d\n",ans); 42 } 43 return 0; 44 }
二进制枚举版：（285ms）
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<cmath> 5 #include<string> 6 #include<algorithm> 7 #define MAXN 1111 8 using namespace std; 9 int cow[MAXN]; 10 int count_digit(int n){ 11 int cnt = 0; 12 for(int i = 0;i < 32;i ++) 13 if(n & (1 << i)) cnt ++; 14 return cnt; 15 } 16 int main(){ 17 int n,m,k,tmp,kind; 18 //freopen("in.c","r",stdin); 19 while(~scanf("%d%d%d",&n,&m,&k)){ 20 memset(cow,0,sizeof(cow)); 21 for(int i = 0;i < n;i ++){ 22 scanf("%d",&tmp); 23 for(int j = 0;j < tmp;j ++){ 24 scanf("%d",&kind); 25 cow[i] |= (1 << (kind-1)); 26 } 27 } 28 int ans = 0; 29 for(int i = 0;i < (1 << m);i ++){ 30 int sum = 0,cnt = 0; 31 if(count_digit(i) > k) continue; 32 for(int j = 0;j < n;j ++) 33 if((cow[j] | i) == i) cnt++; 34 ans = max(ans,cnt); 35 } 36 printf("%d\n",ans); 37 } 38 return 0; 39 }
原文：http://www.cnblogs.com/anhuizhiye/p/3676169.html