【LeetCode周赛】3117. 划分数组得到最小的值之和 | 动态规划

【LeetCode周赛】3117. 划分数组得到最小的值之和 | 动态规划 | 困难

题目内容

原题链接

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

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

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

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

数据范围

1 <= n == nums.length <= 10000
1 <= m == andValues.length <= min(n, 10)
1 <= nums[i] < 100000
0 <= andValues[j] < 100000

题解

为了方便描述，所有下标都从 $1$ 开始。

暴力解法

状态定义

考虑 $d p [j] [i]$ 表示考虑前 $i$ 个元素，前 $j$ 组，第 $j$ 组的最后一个元素是 $n u m s [i]$ 的最小子数组值之和。

状态转移

$dp[j][i]=\min\limits_{k=j-1}^{i-1} (dp[j-1][k]+nums[i])$

时间复杂度： $O(17n^2m)$

优化解法1

可以发现的是，从 $i$ 往前一直进行与运算，整体是一个单调不增的，所以显然可以二分。

二分出最小的 $l$ ，满足 nums[l]&nums[l+1]&...&nums[i]=andValues[j]
二分出最大的 $r$ ，满足 nums[r]&nums[r+1]&...&nums[i]=andValues[j]

然后 $dp[j][i]=\min\limits_{k=l}^{r} (dp[j-1][k]+nums[i])$

这部分的 $\min\limits_{k=l}^{r} (dp[j-1][k])$ 是可以用一个 RMQ 来维护的。

时间复杂度： $O(17nm\log n)$

优化解法 2

上述因为满足单调性，所以考虑双指针。

整体维护一个 $l$ 和 $r$ ，可以发现的是，当 $i$ 递增时， $l$ 和 $r$ 也是单调不减的，所以类似双指针的做法维护 $l$ 和 $r$ ，使得满足上述情况即可。

时间复杂度： $O (17 nm)$

代码

class Solution {
public:
    int minimumValueSum(vector<int>& nums, vector<int>& andValues) {
        const int MAXBIT = 17;
        const int INF = 0x3f3f3f3f;
        int n = nums.size();
        int m = andValues.size();

        nums.insert(nums.begin(), 0);
        andValues.insert(andValues.begin(), 0);
        // dp[j][i] 表示前 j 组和前 i 个元素，第 j 组的最后一个元素是 nums[i] 的情况下的最小权值和
        // dp[j][i] = min(dp[j - 1][k]) + nums[i]
        // 考虑 i ，满足 [k + 1, i]

        vector<vector<int>> pre(MAXBIT, vector<int>(n + 1));
        for (int j = 0; j < MAXBIT; ++j)
            for (int i = 1; i <= n; ++i)
                pre[j][i] = pre[j][i - 1] + (nums[i] >> j & 1);


        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INF));
        dp[0][0] = 0;

        vector<vector<int>> rmq(MAXBIT, vector<int>(n + 1, INF));
        vector<int> lg(n + 1);
        for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;

        auto update = [&](vector<int>& val) {
            for (int i = 0; i <= n; ++i) rmq[0][i] = val[i];
            for (int j = 1; j < MAXBIT; ++j)
                for (int i = 0; i + (1 << j) - 1 <= n; ++i)
                    rmq[j][i] = min(rmq[j - 1][i], rmq[j - 1][i + (1 << (j - 1))]);
        };

        auto query = [&](int l, int r) {
            if (l > r) return INF;
            int len = r - l + 1;
            int b = lg[len];
            return min(rmq[b][l], rmq[b][r - (1 << b) + 1]);
        };

        update(dp[0]);

        auto check = [&](int l, int r, int andV) -> int {
            int res = 0;
            for (int j = 0; j < MAXBIT; ++j)
                if (pre[j][r] - pre[j][l - 1] == r - l + 1)
                    res |= 1 << j;
            // 0 表示整过了
            if ((res & andV) != andV) return 0;
            // 1 表示 res == andV
            if (res == andV) return 1;
            // 2 表示 andV 是 res 的子集
            return 2;
        };

        for (int j = 1; j <= m; ++j) {
            int andV = andValues[j];
            int l = j, r = j;
            for (int i = j; i <= n; ++i) {
                /*
                    优化点在于：
                    我们看暴力的部分：
                        从后往前枚举，什么时候 break ？
                        当 (mask & andV) != andV ，就可以 break 了
                        这部分可以二分，为什么可以二分？
                        因为我们从 i 往前枚举 pi ，这个 mask 在每个二进制位以及整体都是单调下降的

                        二分出 res == andV 的最小的 l
                        继续二分出 res == andV 的最大的 r
                */
                // 暴力解法做法
                // int mask = -1;
                // for (int pi = i; pi >= 1; --pi) {
                //     mask &= nums[pi];
                //     if (mask == andV) dp[j][i] = min(dp[j][i], dp[j - 1][pi - 1] + nums[i]);
                //     if ((mask & andV) != andV) break;
                // }

				// 优化解法1，二分做法
                //int left = j, right = i;
                //while (left < right) {
                //    int mid = (left + right) >> 1;
                //    if (check(mid, i, andV) == 0) left = mid + 1;
                //    else right = mid;
                //}
                //
                //int flag = check(left, i, andV);
                //if (flag != 1) continue;
                //int l = left;
                //
                //right = i;
                //while (left < right) {
                //    int mid = (left + right + 1) >> 1;
                //    if (check(mid, i, andV) == 1) left = mid;
                //    else right = mid - 1;
                //}
                //int r = left;
				
				// 优化解法2双指针做法
                // 首先 l 应该是 == 0 的全部崩掉
                while (l < i && check(l, i, andV) == 0) l += 1;
                if (check(l, i, andV) != 1) continue;

                r = l;
                while (r < i && check(r, i, andV) == 1) r += 1;
                if (check(r, i, andV) == 2) r -= 1;
                dp[j][i] = min(dp[j][i], query(l - 1, r - 1) + nums[i]);
            }

            update(dp[j]);
        }
        return dp[m][n] >= INF ? -1 : dp[m][n];
    }
};