6007. 数组的最大与和

Link

https://leetcode-cn.com/problems/maximum-and-sum-of-array/

Meaning

1. 长度为 $n$ 的数组 $nums$
2. 有 $numSlots$ 个篮子，编号 $1…numSlots$
3. $nums$ 中每个数字都需要放入篮子中
4. 每个篮子最多放两个数字
5. 每个篮子的权值是（篮子中的每个数字与篮子编号的与操作之和）
6. 一种分配方式的权值和是（所有篮子权值之和）
7. 求最大的权值和
8. $n == nums.length$
9. $1 <= numSlots <= 9$
10. $1 <= n <= 2 * numSlots$
11. $1 <= nums[i] <= 15$

Solution

1. 每个篮子最多 $2$ 个整数，可看作 $2*numsSlots$ 个篮子
2. 数据范围小，可以状压 $DP$
3. 篮子的编号不能变，nums中的位置信息不重要
4. 二进制数 $x$ 表示 $2*numSlots$ 个篮子是否被占有
5. 设 $i$ 的二进制中的 $1$ 的个数为 $c$，定义 $f[i]$ 表示将 $nums$ 的前 $c$ 个数字放到篮子中，且放了数字的篮子集合为 $i$ 时的最大与和。初始值 $f[0]=0$
6. 枚举空蓝子的位置 j，对应篮子编号为 j/2+1
7. f[i+2^j] = max( f[i+2^j], f[i] + (j/2+1)&nums[c] )
8. 当然倒过来转移也可行
9. f[i] = max( f[i], f[i-2^j] + (j/2+1)&nums[c-1] )

Code

import static java.lang.Math.max;

class Solution {
    public int maximumANDSum(int[] nums, int numSlots) {
        int tot = (1<<(numSlots<<1));
        int n = nums.length;
        int[] dp = new int[tot];
        int ans = 0;

//        for (int i = 1; i < tot; i++) {
//            int cnt = Integer.bitCount(i);
//            if (cnt > n) continue;
//            for (int j = 0; j < (numSlots<<1); j++) {
//                if (((i >> j) & 1) == 1){
//                    dp[i] = max(dp[i], dp[i-(1<<j)] + ((j/2+1)&nums[cnt-1]));
//                }
//            }
//            if (cnt == n) ans = max(ans, dp[i]);
//        }

        for (int i = 0; i < tot; i++) {
            int cnt = Integer.bitCount(i);
            if (cnt >= n) continue;
            for (int j = 0; j < (numSlots<<1); j++) {
                if (((i >> j) & 1) == 0){
                    dp[i|(1<<j)] = max(dp[i|(1<<j)], dp[i] + ((j/2+1)&nums[cnt]));
                    ans = max(ans, dp[i|(1<<j)]);
                }
            }
        }

        return ans;
    }
}