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)); }}