【状压dp】【bitset】bzoj1688 [Usaco2005 Open]Disease Manangement 疾病管理

vs(i)表示患i这种疾病的牛的集合。

f(S)表示S集合的病被多少头牛患了。

枚举不在S中的疾病i，把除了i和S之外的所有病的牛集合记作St。

f(S|i)=max{f(S)+((St|vs(i))^St)中牛的数量}

#include<cstdio>
#include<bitset>
#include<algorithm>
using namespace std;
bitset<1000>vs[15],t,t2;
int n,m,K,ans,f[1<<15];
int main()
{
//  freopen("bzoj1688.in","r",stdin);
    int x,y;
    scanf("%d%d%d",&n,&m,&K);
    for(int i=1;i<=n;++i)
      {
        scanf("%d",&x);
        if(!x) ++f[0];
        for(int j=1;j<=x;++j)
          {
            scanf("%d",&y);
            vs[y-1][i-1]=1;
          }
      }
    for(int i=0;i<(1<<m);++i)
      for(int j=0;j<m;++j)
        if(!((1<<j)&i))
          {
            t.reset();
            for(int k=0;k<m;++k)
              if((!((1<<k)&i))&&k!=j)
                t|=vs[k];
            f[i|(1<<j)]=max(f[i|(1<<j)],f[i]+(int)((t|vs[j])^t).count());
          }
    for(int i=0;i<(1<<m);++i)
      {
        int cnt=0;
        for(int j=0;j<m;++j)
          if((1<<j)&i)
            ++cnt;
        if(cnt<=K)
          ans=max(ans,f[i]);
      }
    printf("%d
",ans);
    return 0;
}