ZOJ-3305* 二进制子集划分

3305：有N中调料，M种配方。调料每种只能用一次，求能实现多少种配方。
即统计能划分出多少备选子集。


思路：本题代码参考自http://akheyun.blog.163.com/blog/static/13824927620102183300293/
核心思想是二进制表现。
x = (x - 1) & st 实现了子集遍历
比如 st=1110
1101 & 1110 = 1100
1011 & 1110 = 1010
1001 & 1110 = 1000
0111 & 1110 = 0110
0101 & 1110 = 0100
0011 & 1110 = 0010
0001 & 1110 = 0000

联想起求一个数的二进制中1有多少。
用到 x = (x-1) & x  这每次会使一个1变为0 用时可以小于O(n)

#include<iostream>
using namespace std;
#include<stdio.h>
#include<memory.h>

const int M = 1 << 16 + 1;
bool a[M];
int dp[M];

int solve(int st)
{
         int i;
         if (dp[st] != -1) return dp[st]; //已经计算过，直接返回
         dp[st] = 0;
         for (int x = st; x != 0; x = (x - 1) & st)
         {
               //不使用x能达到的配方数和使用x后配方数的最大值
               if (a[x])
                   dp[st] = max(dp[st], solve(st - x) + 1);
         }
         return dp[st];
}

 

int main ()
{

         int i, j, n, m, k, p;
         while (scanf("%d%d", &n, &m) != EOF)
         {
               memset(a, false, sizeof(a));
               memset(dp, -1, sizeof(dp));

               for (i = 0; i < m; i++)
               {
                    scanf("%d", &k);
                    j = 0;
                    while (k--)
                    {
                          scanf("%d", &p);
                          j += (1 << (p - 1)); //每种配方用2进制表示
                    }
                    a[j] = 1;
               }            

			   //初始全为1传入
               printf("%d\n", solve((1 << n) - 1));
         }

}