UVA11825 Hackers' Crackdown

状压DP

首先感谢lrj的透彻讲解.

我们要使一项服务瘫痪，就必须选择一些计算机，使它们与他们所相连的计算机是所有的计算机，即：我们将每一个计算机本身及其相连的计算机看成一个集合\(P_i\)，我们要分成尽量多的集合，使每一个集合里\(Pi∪...∪Pj\)为全集。

我们又发现n的值比较小，因此我们可以考虑一下状压，\(P_i\)的每一位表示\(i\)号计算机的联通情况，\(C_i\)(这是数组，不是组合数)表示我们选择该二进制位下所选择的计算机的并集，\(f(C_i)\)表示在二进制下\(C_i\)可以分成的最大答案。

那么我们就要枚举全集子集的子集，对于子集，我们循环就行了，对于子集的子集，我们这样写就行了（虽然我也不知道为什么）学长说记住就行了

for(int S=0;S<=maxn;++S)//全集的子集 
for(int s0=S;s0;s0=(s0-1)&S)//全集的子集的子集

关于这样的时间复杂度，我们知道一个大小为\(n\) 的集合的子集的个数是\(2^n=\sum_{k=0}^{n}C_{n}^{k}\)（这里是组合数）,那么一个集合的子集的子集的个数就是\(\sum_{k=0}^{n} C_{n}^{k}2^k\),根据二项式定理\((a+b)^k=\sum_{k=0}^{n}C_n^k a^kb^{n-k}\),我们逆用后就能得到原式为\((2+1)^n=3^n\),所以时间复杂度为\(O(3^n)\)O(能过)

剩下的就是一个简单的DP啦

另外用位运算也可以优化一下常数。

最后献上我丑陋的代码。

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m,x,maxn,my_case;
int p[21],c[1<<18],f[1<<18];
int main()
{
    while(scanf("%d",&n)&&n)
    {
        maxn=(1<<n)-1;
        memset(c,0,sizeof(c));memset(f,0,sizeof(f));
        for(int i=0;i<n;++i)
        {
            p[i]=(1<<i);scanf("%d",&m);
            while(m--){scanf("%d",&x);p[i]|=(1<<x);}
        }
        
        for(int S=0;S<=maxn;++S)
            for(int i=0;i<n;++i) if(S&(1<<i))c[S]|=p[i];
        
        for(int S=0;S<=maxn;++S)//全集的子集 
            for(int s0=S;s0;s0=(s0-1)&S)//全集的子集的子集 
            if(c[s0]==maxn)f[S]=max(f[S],f[S-s0]+1);
        
        printf("Case %d: %d\n",++my_case,f[maxn]);
    }
    return 0;
}