Billchenchina 标签 联系 友链

BZOJ1688 Disease Manangement

Posted by Billchenchina on August 10, 2017
标签: 题解 BZOJ

权限题

Click Me To Submit

大致题意

有N头牛,它们共有D种病,现在从这些牛中选出若干头来,使选出来的牛的集合中不超过K种病。

输入

第1行:3个整数N,D,K

第2..N+1行:每行表示一头奶牛的疾病列表,第1个数d_i(1<= d_i<=D)表示该头牛携带d_i种疾病。

接下来的d-i个数,表示该牛携带的疾病编号。

输出

一个整数。表示约翰最多给多少头牛挤奶。

Sample Input&Output

样例输入

6 3 2

0

1 1

1 2

1 3

2 2 1

2 2 1

样例输出

5

题解

水状压DP,可是第一次做还卡了半天…

将每个牛用一个 int 存起来,从右往左数第 $i-1$ 位(二进制)为第$i$种病在奶牛身上的情况,$1$则有病,$0$则没病(见inline void add(int&,int)

然后$for$循环里$i$枚举每种集体得病情况,也为二进制表示,每次循环检查$i$是否合法,如果合法,则算出有几头奶牛符合这个($i$)情况,大于maxn则更新…就OK了…

注意

__builtin_popcount(int)是内建函数,可以直接用来数一个数字里二进制有几个1。

二进制用 if(a|b==b) 或者 ` if(a&b==a) ` 检查a是否为b二进制意义上的子集

代码

#include <bits/stdc++.h>
using namespace std;

inline void add(int &cow,int place) {
    cow|=(1<<(place-1));
}
int main() {
    int N,D,K;
    cin>>N>>D>>K;
    vector<int>cow(N,0);
    for(int i=0; i<N; ++i) {
        int amount;
        cin>>amount;
        for(int j=0; j<amount; ++j) {
            int _d;
            scanf("%d",&_d);
            add(cow[i],_d);
        }
    }
    int maxn=0;
    for(int i=0; i<(1<<D); ++i) {
        // if the i is legal
        if(__builtin_popcount(i)<=K){
            int ttl=0;
            for(int j=0;j<N;++j) {
                // if the cow[j] can be calculated in answer
                if((cow[j]|i)==i)ttl++;
            }
            if(ttl>maxn)maxn=ttl;
        }
    }
    cout<<maxn;
}