Hackers’ Crackdown-----UVA11825-----DP+状态压缩

题目地址：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2925

题目意思：

有N台机器，每台机器上有N个服务

你可以对每台机器选择关闭他以及和他相邻的机器的一种服务

当所有机器不能运行一个服务时，就是摧毁了一种服务

问你最多能摧毁多少个服务

解题思路：

这道题是大白上DP的一道例题，十分经典

对于每一个机器机器相邻的机器我们叫做Pi

那么我们就是要将Pi（i from 1 to n）尽量多的分组，使得他们的并为全集

然后在这个分组里面就可以摧毁一个服务，尽量多的分组，就是为了尽量多的摧毁服务

集合的表示和以用二进制来做，这个十分的经典

然后我们再来枚举分组的组合，用S来表示，COVER[S]就是表示这个分组的并

那么我们可以找到一个递推式

令F[S]表示以S分组的摧毁数，那么F[S] = MAX(F[S^S0],COVER[S0]为全集)+1，这里要想清楚为什么

因为S0是S的一个子集，当S0的并为全集的时候，就相当于在S0的补集上+1了，这样就清楚了

其中LRJ的代码中枚举子集的代码页很美，可以自己观摩观摩

代码本身就是学的大白的，只是说说自己的体会，见笑了。

代码：

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn = 1<<17;

int f[maxn];

int cover[maxn];

int n,m;

int p[20];

int main()

{

    int ca=1;

    while(~scanf("%d",&n) && n)

    {

        for(int i=0;i<n;i++)

        {

            scanf("%d",&m);

            int x;

            p[i] = 1<<i;

            while(m--)

            {

                scanf("%d",&x);

                p[i] |= (1<<x);

            }

        }

        for(int s=0;s<(1<<n);s++)

        {

            cover[s] = 0;

            for(int i=0;i<n;i++)

            {

                if(s & (1<<i))

                    cover[s] |= p[i];

            }

        }

        f[0]=0;

        int all = (1<<n)-1;

        for(int s=1;s<(1<<n);s++)

        {

            f[s]=0;

            for(int s0=s;s0;s0=(s0-1)&s)

            {

                if(cover[s0]==all)

                    f[s] = max(f[s],f[s^s0]+1);//这里的解释是当S中的自己S0可以的时候，这相对于补集+1

            }

        }

        printf("Case %d: %d\n",ca++,f[all]);

    }

    return 0;

}