首页 > 代码库 > POJ 2436

POJ 2436

枚举病的组合,再把牛的状态与之作或运算,若值仍是病组合的状态,则可以加1,否则,跳过。

#include <iostream>#include <algorithm>#include <cstdio>using namespace std;int cow[1100],n,D,K;int ans;int hm(int k){	int h=0;	while(k){		if(k&1)		h++;		k>>=1;	}	return h;}int main(){	int t,status,d;	while(scanf("%d%d%d",&n,&D,&K)!=EOF){		ans=0;		int cc;		for(int i=1;i<=n;i++){			scanf("%d",&t);			status=0;			for(int s=0;s<t;s++){				scanf("%d",&d);				d--;				status=status|(1<<d);			}			cow[i]=status;		}		int s=(1<<D)-1;		for(int i=0;i<=s;i++){			cc=0;			if(hm(i)>K) continue;			for(int k=1;k<=n;k++){				if((i|cow[k])==i)				cc++;			}			if(cc>ans)			ans=cc;		}		printf("%d\n",ans);	}	return 0;}

  

POJ 2436