class Solution {
public:
int defendSpaceCity(vector<int>& time, vector<int>& position) {
}
};
LCP 53. 守护太空城
各位勇者请注意，力扣太空城发布陨石雨红色预警。
太空城中的一些舱室将要受到陨石雨的冲击，这些舱室按照编号 0 ~ N 的顺序依次排列。为了阻挡陨石损毁舱室，太空城可以使用能量展开防护屏障，具体消耗如下：
2 31已知陨石雨的影响范围和到达时刻，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 <= 5001 <= time[i] <= 50 <= position[i] <= 100原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 2.2 MB, 提交时间: 2023-10-27 00:01:22
func defendSpaceCity(time, position []int) int {
const n, m = 100, 1 << 5
rain := [n + 1]int{}
for i, t := range time {
rain[position[i]] |= 1 << (t - 1)
}
var union, single [m]int
for i := 1; i < m; i++ {
lb := i & -i
j := i ^ lb
lb2 := j & -j
if lb == lb2>>1 { // 两个时间点相邻
union[i] = union[j] + 1
single[i] = single[j] + 1 // 递推
} else {
// 若 i 的二进制包含 101，对于联合屏障选择继续维持是更优的，
// 不过下面的 DP 已经枚举了所有的情况，自然会选择更优的方案
union[i] = union[j] + 3
single[i] = single[j] + 2
}
}
// f[i][j] 表示考虑前 i 个舱室，且第 i 个舱室与第 i+1 个舱室开启联合屏障的时间点集合为 j 时，所需的最小能量。
f := [n + 1][m]int{}
for j := range f[0] {
f[0][j] = union[j] + single[(m-1^j)&rain[0]]
}
for i := 1; i <= n; i++ {
for j := range f[i] {
f[i][j] = math.MaxInt32 / 2
mask := m - 1 ^ j
for pre := mask; ; pre = (pre - 1) & mask { // 枚举 j 的补集 mask 中的子集 pre
cost := f[i-1][pre] + union[j] + single[(mask^pre)&rain[i]]
f[i][j] = min(f[i][j], cost)
if pre == 0 { break }
}
}
}
return f[n][0]
}
func min(a, b int) int { if a > b { return b }; return a }
java 解法, 执行用时: 7 ms, 内存消耗: 39.4 MB, 提交时间: 2023-10-27 00:00:04
class Solution {
public int defendSpaceCity(int[] time, int[] position) {
var n = Arrays.stream(position).max().getAsInt();
var m = 1 << Arrays.stream(time).max().getAsInt();
var rain = new int[n + 1];
for (var i = 0; i < time.length; i++)
rain[position[i]] |= 1 << (time[i] - 1);
var union = new int[m];
var single = new int[m];
for (var i = 1; i < m; i++) {
int lb = i & -i, j = i ^ lb, lb2 = j & -j;
union[i] = union[j] + (lb == (lb2 >> 1) ? 1 : 3); // lb == (lb2 >> 1) 表示两个时间点相邻
single[i] = single[j] + (lb == (lb2 >> 1) ? 1 : 2); // 递推
}
var f = new int[n + 1][m];
for (var j = 0; j < m; j++)
f[0][j] = union[j] + single[((m - 1) ^ j) & rain[0]];
for (var i = 1; i <= n; ++i) {
Arrays.fill(f[i], Integer.MAX_VALUE / 2);
for (var j = 0; j < m; ++j)
// 枚举 j 的补集 mask 中的子集 pre
for (int mask = (m - 1) ^ j, pre = mask; ; pre = (pre - 1) & mask) {
var cost = f[i - 1][pre] + union[j] + single[(mask ^ pre) & rain[i]];
f[i][j] = Math.min(f[i][j], cost);
if (pre == 0) break;
}
}
return f[n][0];
}
}
cpp 解法, 执行用时: 0 ms, 内存消耗: 9.5 MB, 提交时间: 2023-10-26 23:59:53
class Solution {
public:
int defendSpaceCity(vector<int> &time, vector<int> &position) {
int n = *max_element(position.begin(), position.end());
int m = 1 << *max_element(time.begin(), time.end());
int rain[n + 1]; memset(rain, 0, sizeof(rain));
for (int i = 0; i < time.size(); ++i)
rain[position[i]] |= 1 << (time[i] - 1);
int un[m], single[m];
un[0] = single[0] = 0;
for (int i = 1; i < m; ++i) {
int lb = i & -i, j = i ^ lb, lb2 = j & -j;
un[i] = un[j] + (lb == (lb2 >> 1) ? 1 : 3); // lb == (lb2 >> 1) 表示两个时间点相邻
single[i] = single[j] + (lb == (lb2 >> 1) ? 1 : 2); // 递推
}
int f[n + 1][m]; memset(f, 0x3f, sizeof(f));
for (int j = 0; j < m; ++j)
f[0][j] = un[j] + single[((m - 1) ^ j) & rain[0]];
for (int i = 1; i <= n; ++i)
for (int j = 0; j < m; ++j)
// 枚举 j 的补集 mask 中的子集 pre
for (int mask = (m - 1) ^ j, pre = mask;; pre = (pre - 1) & mask) {
int cost = f[i - 1][pre] + un[j] + single[(mask ^ pre) & rain[i]];
f[i][j] = min(f[i][j], cost);
if (pre == 0) break;
}
return f[n][0];
}
};
python3 解法, 执行用时: 72 ms, 内存消耗: 16 MB, 提交时间: 2023-10-26 23:59:41
class Solution:
def defendSpaceCity(self, time: List[int], position: List[int]) -> int:
n, m = max(position), 1 << max(time)
rain = [0] * (n + 1)
for t, p in zip(time, position):
rain[p] |= 1 << (t - 1)
union = [0] * m
single = [0] * m
for i in range(1, m):
lb = i & -i
j = i ^ lb
lb2 = j & -j
union[i] = union[j] + (1 if lb == (lb2 >> 1) else 3) # lb == (lb2 >> 1) 表示两个时间点相邻
single[i] = single[j] + (1 if lb == (lb2 >> 1) else 2) # 递推
f = [[inf] * m for _ in range(n + 1)]
for j in range(m):
f[0][j] = union[j] + single[((m - 1) ^ j) & rain[0]]
for i in range(1, n + 1):
for j in range(m):
pre = mask = (m - 1) ^ j
while True: # 枚举 j 的补集 mask 中的子集 pre
cost = f[i - 1][pre] + union[j] + single[(mask ^ pre) & rain[i]]
f[i][j] = min(f[i][j], cost)
if pre == 0:
break
pre = (pre - 1) & mask
return f[n][0]