题目内容

我们称正整数$A$包含$B$，当且仅当$(A|B)=A$,表示按位或运算，即$B$中的所有为$1$的二进制位，在$A$中都为$1$。

现在给定$n$个正整数$A$;，请你从中选出尽量少的整数，使得所有$A$,都至少被一个你选出来的整数包含。

显然任何一个数总是包含其自身，即选择全部的数必定为一组合法答案(但不一定是最少的)。

思路：状态压缩动态规划

前置知识:二进制集合操作 , 动态规划

考虑如果一个数Ai存在超集，那么Ai可以被删掉。考虑求解dp[x]含义为x的超集是否存在，使用状态压缩动态规划套路进行转移。查询dp[Ai]来删除数.

转移方程为:$dp[i] |= dp[j] or (j \in A)$ , 其中j是二进制位恰好比i多一个的所有数.A是数组集合.

其他细节全部写在代码注释里了，大家查看!