LeetCode2172 数组的最大与和

发表于 | 分类于 |
字数统计: 485 | 阅读时长 ≈ 2

链接： https://leetcode-cn.com/problems/maximum-and-sum-of-array/
周赛第四题，比赛的时候直接放弃了，虽然发现数据范围很小，但是忘记状压dp了（太久没用了）

题面

给你一个长度为 n 的整数数组 nums 和一个整数 numSlots ，满足2 * numSlots >= n。总共有 numSlots 个篮子，编号为 1 到 numSlots。
你需要把所有 n 个整数分到这些篮子中，且每个篮子至多有2个整数。一种分配方案的与和定义为每个数与它所在篮子编号的按位与运算结果之和。

解法

数据量很小，考虑状压dp，将状态表示为一个三进制数
定义dp[i][mask]为考虑 nums 中的前 i 个整数，且篮子的可用状态为 mask 时的数组的最大与和。
其中，maskmask是一个三进制数，举个例子， 三进制数1022从低位到高位依次为 2, 2, 0, 1，表示篮子 1 还可以放 2 个数，篮子 2 还可以放 2 个数，篮子 3 还可以放 0 个数，篮子 4 还可以放 1 个数。
令 M 为 $3 ^ {numSlots}$，dp[n][M - 1]为最后的答案
当要把 nums 的第 i 个数放到哪个篮子里。假设要放到第 k 个篮子，那么第 k 个篮子必须还有剩余的空位，此时有

根据上述转移方程即可完成代码

代码

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 M = pow(3, numSlots), n = nums.size();
        vector<vector<int>> dp(n + 1, vector<int>(M));
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < M; j++) {
                int t = j, w = 1;
                for (int k = 1; k <= numSlots; k++) {
                    if (t % 3) {
                        dp[i][j] = max(dp[i][j], dp[i - 1][j - w] + (nums[i - 1] & k));
                    }
                    w *= 3;
                    t /= 3;
                }
            }
        }
        return dp[n][M - 1];

    }
};