守护太空城

标签: 位运算 数组 动态规划 状态压缩

难度: Hard

各位勇者请注意，力扣太空城发布陨石雨红色预警。

太空城中的一些舱室将要受到陨石雨的冲击，这些舱室按照编号 0 ~ N 的顺序依次排列。为了阻挡陨石损毁舱室，太空城可以使用能量展开防护屏障，具体消耗如下：

  • 选择一个舱室开启屏障，能量消耗为 2
  • 选择相邻两个舱室开启联合屏障，能量消耗为 3
  • 对于已开启的 一个 屏障，多维持一时刻，能量消耗为 1

已知陨石雨的影响范围和到达时刻，time[i] 和 position[i] 分别表示该陨石的到达时刻和冲击位置。请返回太空舱能够守护所有舱室所需要的最少能量。

注意：

  • 同一时间，一个舱室不能被多个屏障覆盖
  • 陨石雨仅在到达时刻对冲击位置处的舱室有影响

示例 1：

输入：time = [1,2,1], position = [6,3,3]

输出：5

解释：时刻 1，分别开启编号 3、6 舱室的屏障，能量消耗 2*2 = 4。时刻 2，维持编号 3 舱室的屏障，能量消耗 1。因此，最少需要能量 5。

示例 2：

输入：time = [1,1,1,2,2,3,5], position = [1,2,3,1,2,1,3]

输出：9

解释：时刻 1，开启编号 1、2 舱室的联合屏障，能量消耗 3。时刻 1，开启编号 3 舱室的屏障，能量消耗 2 。时刻 2，维持编号 1、2 舱室的联合屏障，能量消耗 1。时刻 3，维持编号 1、2 舱室的联合屏障，能量消耗 1。时刻 5，重新开启编号 3 舱室的屏障，能量消耗 2。因此，最少需要能量 9。

提示：

  • 1 <= time.length == position.length <= 500
  • 1 <= time[i] <= 5
  • 0 <= position[i] <= 100

Submission

运行时间: 50 ms

内存: 16.1 MB

class Solution:
    def defendSpaceCity(self, time: List[int], position: List[int]) -> int:
        rain = [0]*(max(position)+1)
        maxT = max(time)
        for t, p in zip(time, position):
            rain[p] |= 1<<(t-1)
        mT = 1 << maxT
        u = [0]*mT
        s = [0]*mT
        for mask in range(1, 1<<maxT):
            lb = mask & -mask
            mask1 = mask ^ lb
            lb2 = mask1 & -mask1
            u[mask] = u[mask1] + (1 if (lb<<1) == lb2 else 3) 
            s[mask] = s[mask1] + (1 if (lb<<1) == lb2 else 2) 
        states, states1 = [inf]*mT, [inf]*mT
        for mask in range(mT):
            states[mask] = u[mask] + s[((mT-1)^mask) & rain[0]]
        for rainMask in rain[1:]:
            for mask in range(mT):
                states1[mask] = inf
                pre = m = (mT-1)^mask
                while True:
                    cost = states[pre] + u[mask] + s[(m ^ pre) & rainMask]
                    states1[mask] = min(states1[mask], cost)
                    if pre == 0: break
                    pre = (pre - 1) & m
            states, states1 = states1, states
        return states[0]

Explain

这个问题可以通过使用动态规划来解决。首先，为了处理这些陨石的影响，我们需要知道每个位置在不同时间的状态。我们用一个位掩码来表示每个位置在各个时刻是否会受到陨石的影响。接着，我们定义两个动态规划数组，分别用来存储每个状态的最小能量消耗。具体来说，我们考虑每个位置的每个时间点，检查所有可能的前一个状态，计算从前一个状态转移到当前状态所需的最小能量，并更新当前状态的最小能量。这个过程涉及到位运算和状态压缩，是一个较为复杂的动态规划问题。

时间复杂度: O(P * (2^T)^2)

空间复杂度: O(2^T)

class Solution:
    def defendSpaceCity(self, time: List[int], position: List[int]) -> int:
        # Initialize rain impact array based on the positions and times
        rain = [0] * (max(position) + 1)
        maxT = max(time)
        for t, p in zip(time, position):
            rain[p] |= 1 << (t - 1)

        # Precompute the single and maintain costs for all bitmask states
        mT = 1 << maxT
        u = [0] * mT
        s = [0] * mT
        for mask in range(1, mT):
            lb = mask & -mask
            mask1 = mask ^ lb
            lb2 = mask1 & -mask1
            u[mask] = u[mask1] + (1 if (lb << 1) == lb2 else 3)
            s[mask] = s[mask1] + (1 if (lb << 1) == lb2 else 2)

        # Dynamic programming over states
        states, states1 = [float('inf')] * mT, [float('inf')] * mT
        states[0] = u[0] + s[(mT - 1) ^ rain[0]]
        for rainMask in rain[1:]:
            for mask in range(mT):
                states1[mask] = float('inf')
                pre = m = (mT - 1) ^ mask
                while True:
                    cost = states[pre] + u[mask] + s[(m ^ pre) & rainMask]
                    states1[mask] = min(states1[mask], cost)
                    if pre == 0: break
                    pre = (pre - 1) & m
            states, states1 = states1, states
        return states[0]

Explore

在这种动态规划问题中，使用两个数组'states'和'states1'进行交替更新是为了避免在更新过程中覆盖或混淆前一个时间点的状态值。在每一轮计算中，一个数组用于保存当前时间点的最小能量消耗值，而另一个数组保存上一个时间点的值。这样，我们可以保证在计算当前状态的最小能量时，有一个准确且未被修改的前一个状态参考，从而确保动态规划的正确性和效率。在每个时间点的计算完成后，两个数组的角色会交换，以准备下一个时间点的计算。

这行代码用于生成当前状态掩码'm'的所有可能的子掩码，它是状态压缩动态规划中常见的技术，用于遍历所有子集。在这个特定的代码中，'pre'变量初始化为'm'的补码（即所有未被当前掩码覆盖的位都被设置为1），然后递减'pre'并与'm'进行按位与操作，这样可以确保只考虑'm'的有效位。这种操作可以生成'm'的所有子集，包括空集，从而允许我们在动态规划中考虑所有可能的前一个状态。每次循环生成的'pre'都是'm'的一个有效子集，直到'pre'变为0，即不包含任何有效位，循环结束。这种方法有效地利用位操作来遍历子集，从而提高状态转移的效率。