题目描述

给你两个数组 nums 和 andValues，长度分别为 n 和 m。

数组的 值 等于该数组的 最后一个 元素。

你需要将 nums 划分为 m 个 不相交的连续 子数组，对于第 i 个子数组 [l_i, r_i]，子数组元素的按位 AND 运算结果等于 andValues[i]，换句话说，对所有的 1 <= i <= m，nums[l_i] & nums[l_i + 1] & ... & nums[r_i] == andValues[i]，其中 & 表示按位 AND 运算符。

返回将 nums 划分为 m 个子数组所能得到的可能的 最小 子数组 值 之和。如果无法完成这样的划分，则返回 -1。

样例

输入： nums = [1,4,3,3,2], andValues = [0,3,3,2]

输出： 12

解释：

唯一可能的划分方法为：

[1,4] 因为 1 & 4 == 0
[3] 因为单元素子数组的按位 AND 结果就是该元素本身
[3] 因为单元素子数组的按位 AND 结果就是该元素本身
[2] 因为单元素子数组的按位 AND 结果就是该元素本身
这些子数组的值之和为 4 + 3 + 3 + 2 = 12

输入： nums = [2,3,5,7,7,7,5], andValues = [0,7,5]

输出： 17

解释：

划分 nums 的三种方式为：

[[2,3,5],[7,7,7],[5]] 其中子数组的值之和为 5 + 7 + 5 = 17
[[2,3,5,7],[7,7],[5]] 其中子数组的值之和为 7 + 7 + 5 = 19
[[2,3,5,7,7],[7],[5]] 其中子数组的值之和为 7 + 7 + 5 = 19
子数组值之和的最小可能值为 17

输入： nums = [1,2,3,4], andValues = [2]

输出： -1

解释：

整个数组 nums 的按位 AND 结果为 0。
由于无法将 nums 划分为单个子数组使得元素的按位 AND 结果为 2，因此返回 -1。

限制

• 1 <= n == nums.length <= 10^4
• 1 <= m == andValues.length <= min(n, 10)
• 1 <= nums[i] < 10^5
• 0 <= andValues[j] < 10^5

算法1

(动态规划，二分，ST 表) $O(nm \log n)$

1. 先思考暴力动态规划的做法。设状态 $f(j, i)$ 表示前 $i$ 个数字，划分为了 $j$ 个连续子数组的最小值。其中 $j$ 的范围是 $[1, m]$，$i$ 的范围是 $[1, n]$。
2. 初始值 $f(0, 0) = 0$，其余为 $+\infty$ 待定。
3. 转移时，对于 $f(j, i)$，倒序枚举前序划分点 $k \in [1, i]$，并动态维护区间 $[k, i]$ 的按位 AND 值。当满足区间 $[k, i]$ 的按位 AND 的值为 $andValues(j)$ 时，转移 $f(j, i) = \min(f(j, i), f(j - 1, k - 1) + nums(i))$。
4. 最终答案为 $f(m, n)$。
5. 上面暴力动态规划的状态数为 $O(mn)$，转移时间为 $O(n)$，总时间复杂度为 $O(n^2m)$，不满足要求。
6. 状态数是没办法减少的，只能想办法减少转移时间。注意到，区间 $[k, i]$ 的按位 AND 值是随着 $k$ 值的减小而不增的，这里可以通过二分快速定位到满足要求的 $k$ 的范围。
7. 二分的判定是需要能快速的求出任意区间的按位 AND 值，由于 AND 可重复操作且满足结合律，这里可以使用 ST 表来在对数时间预处理，在常数时间内查询。
8. 假设对于 $f(j, i)$ 的可转移区间为 $k \in [p_1, p_2-1]$，还需要能快速找到这个区间内的最小的 $f(j - 1, k)$ 值，这一部分也可以通过 ST 表在上一层中预处理，并在常数时间内查询得到。
9. 优化后，转移的时间复杂度为二分的时间 $O(\log n)$，同时还需要维护 ST 表，也是对数的时间。
10. ST 表是一种基于倍增的数据结构，$st(j, i)$ 表示从 $i$ 开始的 $2^j$ 个元素的组合值。查询时，将区间 $[l, r]$ 分为可能重叠的两部分，用这两部分的 $st$ 值做组合得到最终结果。

时间复杂度

• 预处理 AND 值 ST 表的时间复杂度为 $O(n \log n)$。
• 动态规划的状态数为 $O(mn)$，转移时间为 $O(\log n)$。
• 动态规划中维护最小值 ST 表的总时间复杂度为 $O(nm \log n)$。
• 故算法的总时间复杂度为 $O(nm \log n)$。

空间复杂度

• 需要 $O(n(m + \log n))$ 的额外空间存储动态规划的状态和 ST 表。

C++ 代码

const int N = 10001, L = 18, M = 11;
const int INF = 1000000000;

class Solution {
private:
    int v[L][N], log[N], mi[L][N];
    int f[N];

    int get_v(int l, int r) {
        int z = log[r - l];

        return v[z][l] & v[z][r - (1 << z) + 1];
    }

    int binary_search(int ed, int target) {
        int l = 1, r = ed + 1;

        while (l < r) {
            int mid = (l + r) >> 1;
            if (get_v(mid, ed) < target)
                l = mid + 1;
            else
                r = mid;
        }

        return l;
    }

    int get_min(int l, int r) {
        int z = log[r - l];

        return min(mi[z][l], mi[z][r - (1 << z) + 1]);
    }

public:
    int minimumValueSum(vector<int>& nums, vector<int>& andValues) {
        const int n = nums.size(), m = andValues.size();

        log[0] = 0;
        for (int i = 1; i <= n; i++) {
            v[0][i] = nums[i - 1];
            log[i] = (i >> (log[i - 1] + 1)) ? log[i - 1] + 1 : log[i - 1];
        }

        for (int j = 1; (1 << j) <= n; j++)
            for (int i = 1; i + (1 << j) - 1 <= n; i++)
                v[j][i] = v[j - 1][i] & v[j - 1][i + (1 << (j - 1))];

        for (int i = 1; i <= n; i++)
            mi[0][i] = f[i] = INF;

        mi[0][0] = f[0] = 0;

        for (int k = 1; (1 << k) <= n; k++)
            for (int i = 0; i + (1 << k) - 1 <= n; i++)
                mi[k][i] = min(mi[k - 1][i], mi[k - 1][i + (1 << (k - 1))]);

        for (int j = 0; j < m; j++) {
            f[0] = INF;
            for (int i = 1; i <= n; i++) {
                int p1 = binary_search(i, andValues[j]);
                int p2 = binary_search(i, andValues[j] + 1);

                if (p1 < p2)
                    f[i] = get_min(p1 - 1, p2 - 2) + nums[i - 1];
                else
                    f[i] = INF;
            }

            for (int i = 0; i <= n; i++) {
                mi[0][i] = f[i];
                f[i] = INF;
            }

            for (int k = 1; (1 << k) <= n; k++)
                for (int i = 0; i + (1 << k) - 1 <= n; i++)
                    mi[k][i] = min(mi[k - 1][i], mi[k - 1][i + (1 << (k - 1))]);
        }

        if (mi[0][n] >= INF)
            return -1;

        return mi[0][n];
    }
};

算法2

(暴力动态规划) $O(nm \log U)$

1. 换一种方式进行暴力动态规划。设状态 $f(i, j, k)$ 表示前 $i$ 个数字，划分为了 $j$ 个连续子数组，且最后一段连续子数组的 AND 值为 $k$ 的最小值。其中 $i$ 的范围是 $[0, n - 1]$，$j$ 的范围是 $[0, m - 1]$，$k$ 这一维定义为哈希表。
2. 初始值 $f(0, 0, nums(0)) = 0$，其余为 $+\infty$ 待定。
3. 转移时，对于 $f(i, j)$，如果 $j > 0$ 且 $andValues(j - 1)$ 存在于 $f(i - 1, j - 1)$ 中，则第 $i$ 个数字可以新开一个子数组，转移 $f(i, j, nums(i)) = f(i - 1, j - 1, andValues(j - 1)) + nums(i - 1)$。其它情况下，将第 $i$ 个数字和前面的连续子数组合并，转移 $f(i, j, k \text{ AND } nums(i)) = \min(f(i, j, k \text{ AND } nums(i)), f(i - 1, j, k))$。
4. 最终答案为 $f(n - 1, m - 1, andValues(m - 1)) + nums(n - 1)$。注意，如果 $andValues(m - 1)$ 在 $f(n - 1, m - 1)$ 中不存在，则返回 $-1$。
5. 可以使用滚动数组优化掉第一维，提升性能。

时间复杂度

• 动态规划的状态数为 $O(nm \log U)$，其中 $U$ 是最大可能的数字。
• 这是因为对于一个固定起始位置的子数组，其向后最多可以产生 $\log U$ 个不同的 AND 值，转移时间为常数，故总时间复杂度为 $O(nm \log U)$。

空间复杂度

• 使用滚动数组，需要 $O(m \log U)$ 的额外空间存储动态规划的状态。

C++ 代码

const int M = 11;

class Solution {
public:
    int minimumValueSum(vector<int>& nums, vector<int>& andValues) {
        const int n = nums.size(), m = andValues.size();
        unordered_map<int, int> f[M];

        f[0][nums[0]] = 0;
        for (int i = 1; i < n; i++) {
            unordered_map<int, int> g[M];

            for (int j = 0; j < min(m, i + 1); j++) {
                if (j > 0 && f[j - 1].count(andValues[j - 1]))
                    g[j][nums[i]] = f[j - 1][andValues[j - 1]] + nums[i - 1];

                for (const auto &[k, _] : f[j]) {
                    int t = k & nums[i];
                    if (g[j].count(t) == 0 || g[j][t] > f[j][k])
                        g[j][t] = f[j][k];
                }
            }

            for (int j = 0; j < min(m, i + 1); j++)
                f[j] = g[j];
        }

        if (f[m - 1].count(andValues[m - 1]) == 0)
            return -1;

        return f[m - 1][andValues[m - 1]] + nums[n - 1];
    }
};