跳转至

2172. 数组的最大与和

来源第 280 场周赛 Q4难度困难分数2392

题目描述

给你一个长度为 n 的整数数组 nums 和一个整数 numSlots ，满足2 * numSlots >= n 。总共有 numSlots 个篮子，编号为 1 到 numSlots 。

你需要把所有 n 个整数分到这些篮子中，且每个篮子 至多 有 2 个整数。一种分配方案的 与和 定义为每个数与它所在篮子编号的 按位与运算 结果之和。

  • 比方说，将数字 [1, 3] 放入篮子 1 中，[4, 6] 放入篮子 2 中，这个方案的与和为 (1 AND 1) + (3 AND 1) + (4 AND 2) + (6 AND 2) = 1 + 1 + 0 + 2 = 4 。

请你返回将 nums 中所有数放入 numSlots 个篮子中的最大与和。

 

示例 1：

输入：nums = [1,2,3,4,5,6], numSlots = 3
输出：9
解释：一个可行的方案是 [1, 4] 放入篮子 1 中，[2, 6] 放入篮子 2 中，[3, 5] 放入篮子 3 中。
最大与和为 (1 AND 1) + (4 AND 1) + (2 AND 2) + (6 AND 2) + (3 AND 3) + (5 AND 3) = 1 + 0 + 2 + 2 + 3 + 1 = 9 。

示例 2：

输入：nums = [1,3,10,4,7,1], numSlots = 9
输出：24
解释：一个可行的方案是 [1, 1] 放入篮子 1 中，[3] 放入篮子 3 中，[4] 放入篮子 4 中，[7] 放入篮子 7 中，[10] 放入篮子 9 中。
最大与和为 (1 AND 1) + (1 AND 1) + (3 AND 3) + (4 AND 4) + (7 AND 7) + (10 AND 9) = 1 + 1 + 3 + 4 + 7 + 8 = 24 。
注意，篮子 2 ，5 ，6 和 8 是空的，这是允许的。

 

提示：

  • n == nums.length
  • 1 <= numSlots <= 9
  • 1 <= n <= 2 * numSlots
  • 1 <= nums[i] <= 15

解法

方法一：状态压缩 + 动态规划

思考

\(k\) 个篮子各能放至多两个数，与和为 \(\sum(a\mathbin{\&}\textit{slot})\)。把每个篮子拆成两个容量为 \(1\) 的槽位，槽位编号映射回篮子号。\(k\le 9\)，槽位至多 \(18\)，可用子集 DP。

\(f[S]\) 表示已用槽位集合为 \(S\) 时的最大与和，\(|S|\) 个已放数对应 \(\textit{nums}\) 的前缀。枚举 \(S\) 中最后占用的槽 \(j\)，从 \(S\setminus\{j\}\) 转移并加上 \(\textit{nums}[|S|-1]\mathbin{\&}(j/2+1)\)。

答案为 \(f\) 的最大值。

由于每个篮子最多只能放两个数，我们不妨将篮子数乘以 \(2\)，这样每个篮子最多只能放一个数。

接下来，我们定义 \(f[i]\) 表示篮子状态为 \(i\) 时的最大与和，其中 \(i\) 是一个二进制数，表示每个篮子是否放了数。初始时 \(f[0]=0\)。

接下来，我们考虑 \(f[i]\) 如何进行状态转移。

我们可以枚举 \(i\)，记 \(i\) 的二进制表示中 \(1\) 的个数为 \(cnt\)。如果 \(cnt \gt n\)，那么 \(i\) 不是一个合法的状态，我们可以直接跳过。否则，我们可以枚举 \(i\) 的二进制表示中的每一位 \(j\)，如果 \(i\) 的第 \(j\) 位为 \(1\)，那么我们可以将第 \((cnt-1)\) 个数 \(nums[cnt-1]\) 放入第 \(j\) 个篮子中，此时有：

\[ f[i] = \max\{f[i], f[i \oplus (1 << j)] + (nums[cnt-1] \wedge (j / 2 + 1))\} \]

其中 \(\oplus\) 表示异或运算，而 \(\wedge\) 表示按位与运算。

答案为 \(\max\{f[i]\}\)。

时间复杂度 \(O(4^k \times k \times 2)\)，空间复杂度 \(O(4^k)\)。其中 \(k\) 表示篮子的数量，即题目中的 \(numSlots\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:
        n = len(nums)
        m = numSlots << 1
        f = [0] * (1 << m)
        for i in range(1 << m):
            cnt = i.bit_count()
            if cnt > n:
                continue
            for j in range(m):
                if i >> j & 1:
                    f[i] = max(f[i], f[i ^ (1 << j)] + (nums[cnt - 1] & (j // 2 + 1)))
        return max(f)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int maximumANDSum(int[] nums, int numSlots) {
        int n = nums.length;
        int m = numSlots << 1;
        int[] f = new int[1 << m];
        int ans = 0;
        for (int i = 0; i < 1 << m; ++i) {
            int cnt = Integer.bitCount(i);
            if (cnt > n) {
                continue;
            }
            for (int j = 0; j < m; ++j) {
                if ((i >> j & 1) == 1) {
                    f[i] = Math.max(f[i], f[i ^ (1 << j)] + (nums[cnt - 1] & (j / 2 + 1)));
                }
            }
            ans = Math.max(ans, f[i]);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int maximumANDSum(vector<int>& nums, int numSlots) {
        int n = nums.size();
        int m = numSlots << 1;
        int f[1 << m];
        memset(f, 0, sizeof(f));
        for (int i = 0; i < 1 << m; ++i) {
            int cnt = __builtin_popcount(i);
            if (cnt > n) {
                continue;
            }
            for (int j = 0; j < m; ++j) {
                if (i >> j & 1) {
                    f[i] = max(f[i], f[i ^ (1 << j)] + (nums[cnt - 1] & (j / 2 + 1)));
                }
            }
        }
        return *max_element(f, f + (1 << m));
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func maximumANDSum(nums []int, numSlots int) int {
    n := len(nums)
    m := numSlots << 1
    f := make([]int, 1<<m)
    for i := range f {
        cnt := bits.OnesCount(uint(i))
        if cnt > n {
            continue
        }
        for j := 0; j < m; j++ {
            if i>>j&1 == 1 {
                f[i] = max(f[i], f[i^(1<<j)]+(nums[cnt-1]&(j/2+1)))
            }
        }
    }
    return slices.Max(f)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
function maximumANDSum(nums: number[], numSlots: number): number {
    const n = nums.length;
    const m = numSlots << 1;
    const f: number[] = new Array(1 << m).fill(0);
    for (let i = 0; i < 1 << m; ++i) {
        const cnt = i
            .toString(2)
            .split('')
            .filter(c => c === '1').length;
        if (cnt > n) {
            continue;
        }
        for (let j = 0; j < m; ++j) {
            if (((i >> j) & 1) === 1) {
                f[i] = Math.max(f[i], f[i ^ (1 << j)] + (nums[cnt - 1] & ((j >> 1) + 1)));
            }
        }
    }
    return Math.max(...f);
}

评论