BZOJ-1688: [Usaco2005 Open]Disease Manangement 疾病管理

Description

有N头牛,它们可能患有D种病,现在从这些牛中选出若干头来,但选出来的牛患病的集合中不过超过K种病.N<=2000,K<=D<=15

考虑了一下，如果枚举所选疾病集合的话是就是=1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1。最多一个就是6k，直接dfs，然后O(n)通过状压计数就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,d,k,col[2100],ans;
int read()
{
    int re=0; char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9')
        re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
    return re;
}
void dfs(int x,int y,int s)
{
    if(d-x+y<k||x>d) return ;
    if(y==k)
    {
        int tmp=0;
        for(int i=1;i<=n;i++)
            if((col[i]|s)==s) tmp++;
        ans=max(ans,tmp);
        return;
    }
    dfs(x+1,y,s);
    dfs(x+1,y+1,s|(1<<x+1));
}
int main()
{
    n=read(); d=read(); k=read();
    int x,i;
    for(i=1;i<=n;i++)
    {
        x=read(); 
        while(x--) col[i]=col[i]|(1<<read());
    }
    dfs(0,0,0);
    printf("%d",ans);
    return 0;
}