Leetcode.2172 数组的最大与和

题目链接

Leetcode.2172 数组的最大与和 rating : 2392

题目描述

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

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

• 比方说，将数字 $[1,3]$ 放入篮子 $1$ 中，$[4,6]$ 放入篮子 $2$ 中，这个方案的与和为 $(1AND1)+(3AND1)+(4AND2)+(6AND2)=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\le numSlots\le 9$
• $1\le n\le 2\ast numSlots$
• $1\le nums[i]\le 15$

解法：状压dp

我们将原问题转换为 ： 将 $nums$ 中 $n$ 个数字放入到 $2\ast numSlots$ 篮子中，每个篮子最多放入一个数字，求最大 与和。

由于 $2\ast numSlots$ 很小，所以我们可以使用状压dp。

我们定义 $f(i)$ ($i$ 中二进制位 $1$ 的数量为 $c$ )，表示将 $nums$ 中前 $c$ 个数字放入篮子中的最大与和。

假设此时第 $j$ 位的篮子是空的，此时这个篮子的编号为 $j/2+1$，就有：

{ t = i ∣ ( 1 < < j ) f [ t ] = m a x { f [ t ] , f [ i ] + ( j / 2 + 1 ) & n u m s [ c ] \begin{cases} t = i | (1 << j) \\ f[t] = max\{ f[t] , f[i] + (j/2 + 1) \& nums[c] \end{cases} {t=i∣(1<<j)f[t]=max{f[t],f[i]+(j/2+1)&nums[c]​

时间复杂度： $O(2^{2\ast numSlots}\times 2\times numSlots)$

C++代码：

class Solution {
public:
    int maximumANDSum(vector<int>& nums, int slot) {
        int n = nums.size(),len = 1 << (2 * slot);
        vector<int> f(len);


        int ans = 0;
        for(int i = 0;i < len;i++){
            int c = __builtin_popcount(i);
            if(c >= n) continue;
            for(int j = 0;j < 2 * slot;j++){
                //寻找空蓝子,放入数字
                if((i & (1 << j)) == 0){
                    int t = i | (1 << j);
                    f[t] = max(f[t] , f[i] + ((j / 2 + 1) & nums[c]));
                    ans = max(ans , f[t]);
                }
            }
        }

        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24