Description

　　你是一个hacker，侵入了一个有着n台计算机（编号为1.2.3....n）的网络。一共有n种服务，每台计算机都运行着所有服务。对于每台计算机，你都可以选择一项服务，终止这台计算机和所有与它相邻计算机的该项服务（如果其中一些服务已经停止，那他们继续保持停止状态）。你的目标是让尽量多的服务完全瘫痪

Input

输入包含多组数据，每组数据中：

• 第一行为整数n:
• 以下n行每行描述一台计算机相邻的计算机，
• 其中第一个数m为相邻计算机个数，接下来的m个整数为这些计算机的编号。

输入结束标志n=0

Output

对于每组数据：

• 输出完全瘫痪的服务的数量

格式见样例

Sample Input

32 1 22 0 22 0 141 11 01 31 20

Sample Output

Case 1: 3Case 2: 2

Hint

1<=n<=16

Solution

　　考虑对于每种服务，显然需要所有计算机都停掉才有价值。

　　我们设Set_i为i和i相邻的计算机编号的集合。由于数据范围小，显然所有的集合都可以二进制表示，以下不再赘述。

　　那么本题所求就变为将所有的Set最多分为几组，使得每组的Set的并集都为全集。

　　我们设f_i为只考虑集合i中元素的ans。

　　转移显然：

　　f[i]=max{f[i^j]|集合j的set并集为全集且j是i的子集}+1

　　考虑阶段:

　　最简单的方法当然是按照元素个数枚举,但是在本题中难以操作。

　　考虑以下事实 ：

　　设i从j转移过来，那么j为i的子集。在二进制表示下，显然有j≤i。那么按照i升序枚举，显然j在计算i时已经被计算完毕。

　　现在考虑如何高效率枚举i的子集：

　　朴素的枚举方式如下：

int ziji=0;for(int i=0;i

　　考虑优化效率：

for(rg int i=1;i<=upceil;++i) {    for(rg int j=i;j;j=(j-1)&i) {        dosth();    }}

　　内层循环可以高效枚举i的子集，其时间效率为O(|i|)，其中|i|代表i在二进制意义下表示的集合的元素个数.

　　继续考虑优化：

　　在枚举子集后，如果可以快速判断该集合中元素对应的set的并集是否为全集可以大大提高时间效率，这样我们令S0[i]为i在二进制意义下所代表的集合的元素对应的set的并集的二进制（这是什么鬼畜句型。我们可以通过预处理做到O(1)查询并集。

　　预处理时，枚举每个集合，暴力枚举每个元素j是否属于该集合，如果是，则S0[i]|=Set[j]。时间复杂度O(n*2ⁿ)。

　　这样思路就完成了:

　　预处理出计算机i的子集Set,通过枚举选择的计算机编号,进行DP转移。

　　事实上,这是一个状压套状压的题目。我们枚举的是计算机的编号，而判断的是编号所对应的Set的集合的并集是否等于全集。

　　考虑时间复杂度：

　　参照循环，时间复杂度为全集的子集的子集个数和。

　　由于元素个数为x的元素子集有C(n,x)个，每个子集有2^x个子集,所以元素个数为Σ_{(x:1 to n)}C(n,x)*2^x。由二项式定理得，原式=(2+1)ⁿ=3ⁿ

　　所以程序得时间复杂度为θ(3ⁿ+n*2ⁿ)=O(3ⁿ)

Code

#include
     
      #include
      
       #define rg register#define ci const intinline void qr(int &x) {    char ch=getchar(),lst=NULL;    while(ch>'9'||ch<'0') lst=ch,ch=getchar();    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();    if (lst=='-') x=-x;}char buf[20];inline void write(int x,const char aft,const bool pt) {    if(x<0) {putchar('-');x=-x;}    int top=0;    do {        buf[++top]=x%10+'0';        x/=10;    } while(x);    while(top) putchar(buf[top--]);    if(pt) putchar(aft);}template 
       
        inline T mmax(const T &a,const T &b) {
   if(a>b) return a;return b;}template 
        
         inline T mmin(const T &a,const T &b) {
   if(a
         
          inline T mabs(const T &a) {
   if(a<0) return -a;return a;}template 
          
           inline void mswap(T &a,T &b) {T temp=a;a=b;b=temp;}const int maxn = 17;const int maxt = 262144;const int maxm = 400;int n,a,b,cnt,ans;int frog[maxt];int Set[maxn];int s0[maxt];void clear();int main() { qr(n); while(n) { clear(); for(rg int i=0;i
           
            i) break; if(i&k) s0[i]|=Set[j]; } } for(rg int i=1;i<=upceil;++i) { for(rg int j=i;j;j=(j-1)&i) { if(s0[j]==upceil) {frog[i]=mmax(frog[i],frog[j^i]+1);} } ans=mmax(frog[i],ans); } printf("Case %d: %d\n",++cnt,ans); n=0;qr(n); } return 0;}void clear() { memset(s0,0,sizeof s0); memset(Set,0,sizeof Set); memset(frog,0,sizeof frog); ans=0;}
           
          
         
        
       
      
     

Summary

1、子集枚举方式需要牢记。

2、在一些由子集转移来得题目中,可以将集合序号作为阶段。

3、计算复杂的得时候二项式定理会被经常使用

4、在高复杂度问题中，预处理是个好东西。