细菌(disease)
题目描述
近期，农场出现了D(1≤D≤15)种细菌。John要从他的N(1≤N≤1000)头奶牛中尽可能多地选些产奶，但是如果选中的奶牛携带了超过K(1≤K≤D)种不同细菌，所生产的奶就不合格。请你帮助John计算出最多可以选择多少头奶牛。
输入
第1行：三个整数N，D，K。
下面N行：第i行表示一头牛所携带的细菌情况。第一个整数di表示这头牛所携带的细菌种类数，后面di个整数表示这些细菌的各自种类标号。
输出
一个数M，最大可选奶牛数。
样例输入
6 3 2
0
1 1
1 2
1 3
2 2 1
2 2 1
样例输出
5
提示
样例说明：选择l，2，3，5，6头奶牛，只有1#和2#两种细菌。
分析：考虑将数转化为二进制，状态压缩；
代码：
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <climits> #include <cstring> #include <string> #include <set> #include <map> #include <queue> #include <stack> #include <vector> #include <list> #include <ext/rope> #define rep(i,m,n) for(i=m;i<=n;i++) #define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++) #define vi vector<int> #define pii pair<int,int> #define mod 1000000007 #define inf 0x3f3f3f3f #define pb push_back #define mp make_pair #define fi first #define se second #define ll long long #define pi acos(-1.0) const int maxn=3e5+10; const int dis[4][2]={{0,1},{-1,0},{0,-1},{1,0}}; using namespace std; using namespace __gnu_cxx; ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);} ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;} int n,m,ans[maxn],a[1010],ma; int work(int p) { int cnt=0; while(p){if(p&1)cnt++;p>>=1;} return cnt; } int main() { int i,j,k,t; scanf("%d%d%d",&n,&m,&k); rep(i,0,n-1) { scanf("%d",&j); while(j--) { scanf("%d",&t); a[i]+=qpow(2,t-1); } } rep(i,0,qpow(2,m)-1) { if(work(i)>k)continue; rep(j,0,n-1) { if((i|a[j])==i)ans[i]++; } ma=max(ma,ans[i]); } printf("%d ",ma); //system ("pause"); return 0; }
附排除法，排除掉m-k个细菌，剩下的牛取最大值即可；
代码：
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <climits> #include <cstring> #include <string> #include <set> #include <map> #include <queue> #include <stack> #include <vector> #include <list> #include <ext/rope> #define rep(i,m,n) for(i=m;i<=n;i++) #define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++) #define vi vector<int> #define pii pair<int,int> #define mod 1000000007 #define inf 0x3f3f3f3f #define pb push_back #define mp make_pair #define fi first #define se second #define ll long long #define pi acos(-1.0) const int maxn=1e3+10; const int dis[4][2]={{0,1},{-1,0},{0,-1},{1,0}}; using namespace std; using namespace __gnu_cxx; ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);} ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;} int n,m,a[maxn][16],p[maxn],ma; void dfs(int cnt,int now,int p[]) { int q[maxn]={0}; for(int i=1;i<=n;i++) q[i]=a[i][now]||p[i]; if(cnt==1) { int ans=0; for(int i=1;i<=n;i++) if(!q[i])ans++; ma=max(ma,ans); return; } for(int i=now+1;i<=m;i++) { dfs(cnt-1,i,q); } } int main() { int i,j,k,t; scanf("%d%d%d",&n,&m,&k); rep(i,1,n){ scanf("%d",&j); while(j--)scanf("%d",&t),a[i][t]=1; } if(m==k)return 0*printf("%d ",n); rep(i,1,k+1)dfs(m-k,i,p); printf("%d ",ma); //system ("pause"); return 0; }