【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

输出样例 1

提示

选择：1,2,3,5,6只有1#和2#两种细菌

比赛的时候没想出来按照dp的思路想

其实很简单状态压缩并且枚举所有的情况即可

#include<bits/stdc++.h>
using namespace std;
//input
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m);
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define LL long long
#define REP(i,N)  for(int i=0;i<(N);i++)
#define CLR(A,v)  memset(A,v,sizeof A)
//////////////////////////////////
#define N 15

int dp[1<<15];
int a[1005];
int fastpow(int a,int b)
{
     int ans=1;
     while(b)
     {
        if (b&1) ans=ans*a;
         b>>=1;
         a=a*a;
   }
   return ans;
}
int work(int x)
{
    int cnt=0;
    while(x)
    {
        if(x&1)cnt++;
        x>>=1;
    }
    return cnt;
}

int main()
{
    int n,k,d;
    RIII(n,d,k);
    rep(i,1,n)
    {
        int q;cin>>q;
        while(q--)
        {
            int x;cin>>x;
            a[i]|=1<<(x-1);
        }
    }
    int cnt,maxx=0;

    rep(i,0,fastpow(2,d)-1)
    {
        if(work(i)>k)continue;
        cnt=0;
        rep(j,1,n)
        {
            if( (a[j]|i)==i)cnt++;
        }
        if(cnt>maxx)maxx=cnt;

    }
    cout<<maxx;
}

View Code