【noip模拟赛5】细菌
描述
近期，农场出现了D(1<=D<=15)种细菌。John要从他的 N(1<=N<=1,000)头奶牛中尽可能多地选些产奶。但是如果选中的奶牛携带了超过 K (1<=K<=D)种不同细菌，所生产的奶就不合格。请你帮助John 计算出最多可以选择多少头奶牛。
输入
第一行：三个整数N，D，K
下面N行：第i行表示一头牛所携带的细菌情况。第一个整数di表示这头牛所携带的细菌种类数，后面di个整数表示这些细菌的各自种类标号。
输出
只一个数 M，最大可选奶牛数。
输入样例 1
6 3 2
0
1 1
1 2
1 3
2 2 1
2 2 1
输出样例 1
5
提示
背包（dp）类问题，需要枚举掉所有可能 再算哪个最多。
但涉及到一个问题，用数组记录的话，可能会爆空间！
存在哪几个病毒，在d最大只有15的情况下，我把用一个int 各位上的0,1 来表示就ok了，相比于用bool记录，还有利于计算。
所以开两个数组：
1 a[i] 记录第 i 个奶牛有哪几种病毒 ，比如第m种用 a[i]+=1<<(m-1) 来记录。
2 dp[i] 病毒情况为 i 时的最大奶牛数。更新n轮（n只奶牛分别枚举）。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <time.h>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
const int N=;
int n,k,d,m,t;
int a[N],dp[N]; int fun(int x)
{
int c=;
while(x)
{
if(x&)
c++;
x>>=;
}
return c;
} int main()
{
// freopen("input.txt","r",stdin);
cin>>n>>d>>k;
for(int i=; i<n; i++)
{
cin>>t;
for(int j=; j<t; j++)
{
cin>>m;
a[i]+=<<(m-); //状态压缩
}
}
for(int i=;i<n;i++) // 从 0 到 n-1 枚举每只奶牛
{
for(int j=(<<d)-;j>;j--)
{
if(dp[j|a[i]]<dp[j]+) //取大
dp[j|a[i]]=dp[j]+;
}
}
int ans=;
for(int i=;i<<<d;i++)
{
if(fun(i)<=k&&dp[i]>ans)
ans=dp[i];
}
cout<<ans;
return ;
}