3489.零数组变换IV

dp, bit manipulation, https://leetcode.cn/problems/zero-array-transformation-iv/

给你一个长度为 n 的整数数组 nums 和一个二维数组 queries ，其中 queries[i] = [li, ri, vali]。

每个 queries[i] 表示以下操作在 nums 上执行：

从数组 nums 中选择范围 [li, ri] 内的一个下标子集。
将每个选中下标处的值减去正好 vali。

零数组 是指所有元素都等于 0 的数组。

返回使得经过前 k 个查询（按顺序执行）后，nums 转变为 零数组 的最小可能非负值 k。如果不存在这样的 k，返回 -1。

数组的子集是指从数组中选择的一些元素（可能为空）。

示例 1：

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

输出： 2

解释：

对于查询 0 （l = 0, r = 2, val = 1）：
- 将下标 [0, 2] 的值减 1。
- 数组变为 [1, 0, 1]。
对于查询 1 （l = 0, r = 2, val = 1）：
- 将下标 [0, 2] 的值减 1。
- 数组变为 [0, 0, 0]，这就是一个零数组。因此，最小的 k 值为 2。

示例 2：

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

输出： -1

解释：

即使执行完所有查询，也无法使 nums 变为零数组。

示例 3：

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

输出： 4

解释：

对于查询 0 （l = 0, r = 1, val = 1）：
- 将下标 [0, 1] 的值减 1。
- 数组变为 [0, 1, 3, 2, 1]。
对于查询 1 （l = 1, r = 2, val = 1）：
- 将下标 [1, 2] 的值减 1。
- 数组变为 [0, 0, 2, 2, 1]。
对于查询 2 （l = 2, r = 3, val = 2）：
- 将下标 [2, 3] 的值减 2。
- 数组变为 [0, 0, 0, 0, 1]。
对于查询 3 （l = 3, r = 4, val = 1）：
- 将下标 4 的值减 1。
- 数组变为 [0, 0, 0, 0, 0]。因此，最小的 k 值为 4。

示例 4：

输入： nums = [1,2,3,2,6], queries = [[0,1,1],[0,2,1],[1,4,2],[4,4,4],[3,4,1],[4,4,5]]

输出： 4

提示：

1 <= nums.length <= 10
0 <= nums[i] <= 1000
1 <= queries.length <= 1000
queries[i] = [li, ri, vali]
0 <= li <= ri < nums.length
1 <= vali <= 10

python

class Solution:
    def minZeroArray(self, nums: List[int], queries: List[List[int]]) -> int:
        n = len(nums)
        # dp[i] 的二进制位 s 为 1 表示下标 i 可累积减去的和包含 s
        dp = [1] * n  # 初始时仅能达到 0（即二进制 1）
        
        # 如果初始状态就是零数组，则直接返回 0
        if all((dp[i] >> nums[i]) & 1 for i in range(n)):
            return 0
        
        for k, (l, r, v) in enumerate(queries):
            for i in range(l, r + 1):
                dp[i] |= (dp[i] << v)
                dp[i] &= (1 << (nums[i] + 1)) - 1  # 只保留低 nums[i]+1 位
            # 检查所有位置是否都能精确达到 nums[i]
            if all((dp[i] >> nums[i]) & 1 for i in range(n)):
                return k + 1  # k 为 0-indexed，故返回 k+1
        
        return -1

3489.零数组变换IV ​

3489.零数组变换IV