纪中第二天（c组）（1）

题目（1）

近期，农场出现了D (1<= D <=15)种细菌。John 要从他的 N (1<= N <=1,000)头奶牛中尽可能多地选些产奶。但是如果选中的奶牛携带了超过 K (1<= K <=D)种不同细菌，所生产的奶就不合格。请你帮助John 计算出最多可以选择多少头奶牛。

输入

第一行：三个整数 N， D， K

下面N行：第行表示一头牛所携带的细菌情况。第一个整数 di 表示这头牛所携带的细菌种类数，后面di个整数表示这些细菌的各自种类标号。

输出

只一个数 M，最大可选奶牛数。

样例输入

6 3 2         
0
1 1
1 2
1 3
2 2 1
2 2 1

样例输出

5

样例解释

选择：

1,2,3,5,6

只有1#和2#两种细菌

 

思路

因为D才15，所以我们暴力枚举。时间复杂度为O（$C_D^K$）。

 每选出K个数便将所有情况枚一遍。如果出现不符合的变将ans - -，inf存最优解。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,ans,d,k,inf=-0x3f3f3f,use[16],b[16];
bool a[1001][16],flag[16];
void dfs(int x)
{
    for(int i=use[x-1]+1;i<=d;i++)
        if(flag[i]==false)
        {
            flag[i]=true;
            use[x]=i;
            if(x==k)
            {
                for(int j=1;j<=n;j++)
                {
                    for(int i1=1;i1<=d;i1++)
                        if(a[j][i1]==true&&flag[i1]==false)
                        {
                            ans--;
                            break;
                        }
                }
                if(ans>inf)
                    inf=ans;
                ans=n;
            }
            else
                dfs(x+1);
            flag[i]=false;
            use[x]=0;
        }
}
int main()
{
    memset(use,0,sizeof(use));
    memset(flag,false,sizeof(flag));
    scanf("%d%d%d",&n,&d,&k);
    ans=n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[0][0]);
        for(int j=1;j<=a[0][0];j++)
        {
            scanf("%d",&b[i]);
            a[i][b[i]]=true;
        }
    }
    dfs(1);
    printf("%d",inf);
    return 0;
}