2436:Disease Management

keyword

BruteForce　C++

概要

飼っているN(<1000)匹の牛がかかっている病気の種類(<15)が与えられる。そのうちK種類の病気を選んで無効にできる。病気から回復させられる牛の最大数を求める問題。
病気の種類が少ないので全探索する。計算量は最大でも(15,7)*1000なので余裕。

int main(){
    int ns[1004], n, m, i, j, mask, d, k, x, best, cnt;

    scanf("%d%d%d",&n,&d,&k);
    REP(i,n){
        mask = 0;
        scanf("%d",&m);
        REP(j,m){
            scanf("%d",&x);
            mask |= 1<<(x-1);
        }
        ns[i] = mask;
    }

    best = 0;
    REP(mask,1<<d)if(__builtin_popcount(mask)==k){
        cnt = 0;
        REP(i,n)if(!(ns[i] & (~mask)))cnt++;
        best = max(best, cnt);
    }

    printf("%d\n",best);

    return 0;
}