PKU 2436 Disease Management
http://poj.org/problem?id=2436
n匹の牛がいる牧場でd種類の病気がはやっている。
それぞれの牛はdi種類の病気を持っている。
牛から取れる牛乳を混ぜたときに、k種類より多い病気が混入したら捨てなければならない。
最大何匹の牛から取れるかというような問題。
bitの順列を使いました。蟻本を見ずに書けるようになりたいです。
結構時間的に厳しいかと思いましたが、思ったほどではありませんでした。
int st[1000]; main(){ int n,d,k; cin>>n>>d>>k; rep(i,n){ int di; cin>>di; while(di--){ int t; cin>>t; st[i]|=1<<t-1; } } int comb=(1<<k)-1; int ans=0; while(comb<1<<d){ bool ok=true; int tans=0; rep(i,n){ if((st[i]|comb)==comb)++tans; } ans=max(tans,ans); int x=comb&-comb,y=comb+x; comb=((comb&~y)/x>>1)|y; } cout<<ans<<endl; }