algorithm - 使所有数组元素为零的最少 AND 运算次数

Question

我在一次编程竞赛中遇到了这个问题:

We are given an array consisting of n elements. At each iteration, you can select any two elements a_i and a_j and replace a_i with a_i & a_j. & is the bitwise AND operator. Find the minimum number of AND operations needed to make all array elements zero.

Suppose that there is a solution for the given inputs. What is the optimal solution for this problem?

编辑:我已经为运行时间超过 1 秒的问题添加了我的 DP 解决方案。有什么加快速度的建议吗？

0 < n < 65535

D: maximum number of digits in base 2 (0 < D < 17)

GOAL: 2^D - 1

T[i][X] => minimum number of elements from {n_0, n_1, ..., n_i} that make X zero

T[i][0] = 0

T[0][X>0] = INF

T[i][X] = min( 1 + T[i-1][X & n_i] , T[i-1][X] )

T[n][GOAL] -> min number of AND operations

Answer 1

在我看来这就像 set cover problem .我们需要找到在每个位置都覆盖零的最小子集。一旦找到该子集，生成的“绝对”零可用于将其他元素转换为零。在下面的示例中，子集中的三个元素中的任何一个都可以用作第一个零。

1001
0101<
0011<
1110<
0111