黑客的攻击 uva 11825【dp+枚举】

蓝书经典例题

题目大意

将一堆集合分组，使得每个组的并集等于全集，问最多有个多少个这样的集合

题目分析

n很小，所以用二进制来存储集合
cover[s] 记录 s中所包含的几个集合的并集
f[s] 记录能划分成的集合个数

f[s]=max{f[s-s0] s0 是s的子集，且cover[s0] == 全集} +1
时间复杂度 $O\left(C\right(n,k\left)2^k\right)=O\left(3^n\right)$O(C(n,k)2k)=O(3n)
这里有一个枚举子集的骚操作

    for(int i=1;i<(1<<n);i++)
    {
        f[i]=0;
        for(int s=i;s;s=(s-1)&i)
        if(cover[s]==all)   f[i] = max(f[i],f[i^s]+1);
    }
*/

代码详解

#include <bits/stdc++.h>
#define cl(a) memset(a,0,sizeof(a))
#define sc(x) scanf("%d",&x)
#define pt(x) printf("%d\n",x)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int maxn=1e5+50;
const int mod=1e9+7;
typedef long long ll;
int p[20];
int cover[1<<18];
int f[1<<18];
int kase=0;
int main()
{
    int n;
    kase=0;
    while(scanf("%d",&n)&&n)
    {
        cl(f);cl(cover);cl(p);
        for(int i=0;i<n;i++)
    {
        p[i] = (1<<i);
        int m;
        sc(m);
        for(int t=1;t<=m;t++)
        {
            int x;
            sc(x);
            p[i]|=(1<<x);
          //  cout<<(1<<x)<<" "<<p[i]<<endl;
        }
       // cout<<p[i]<<endl;
    }
    for(int i=0;i<(1<<n);i++)
    {
        cover[i]=0;
        for(int j=0;j<n;j++)
        {
            if(i&(1<<j)) cover[i]|=p[j];
        }
        //cout<<cover[i]<<endl;
    }
    f[0]=0;
    int all = (1<<n)-1;
    for(int i=1;i<(1<<n);i++)
    {
        f[i]=0;
        //cout<<f[i]<<endl;
        for(int s=i;s;s=(s-1)&i)
        if(cover[s]==all)   f[i] = max(f[i],f[i^s]+1);
       // cout<<i<<" "<<f[i]<<endl;
    }
    printf("Case %d: %d\n",++kase,f[all]);
    }
    return 0;
}
/*
3
2 1 2
2 0 2
2 0 1
4
1 1
1 0
1 3
1 2
0



*/