尧图网页设计 
实现这道题的核心思路是利用状态压缩动态规划。因为 time[i] 最大只有 5所以可以用一个 5 位的二进制数来表示某个舱室在 5 个时刻的屏障开启情况。问题的难点在于处理相邻舱室的联合屏障我们可以通过枚举上一个舱室在哪些时刻开启了联合屏障来解决。以下是详细解析和可直接运行的Java代码。解题思路1. 数据表示用 rain[p] 的二进制低5位表示位置 p 在哪些时刻有陨石。第 t 时刻有陨石则第 t 位从0开始为1。2. 预处理代价对于任意一个状态 j二进制表示哪些时刻有屏障计算单独开启这些屏障所需的最小能量 single[j]。如果同一个舱室在两个相邻时刻都需要屏障则第二个时刻只需花 1 点能量维持即可否则需要花 2 点能量重新开启。3. 核心DPdp[i][j] 表示处理到第 i 个舱室且第 i 个舱室与第 i1 个舱室在时刻集合 j 开启联合屏障时的最小总能量。· 当计算 dp[i][j] 时枚举上一个舱室 i-1 的联合屏障时刻集合 pre。注意 pre 和 j 不能有交集因为一个时刻一个舱室不能被两个屏障覆盖。· 状态转移方程dp[i][j] min(dp[i-1][pre] cost)。· 这个 cost 是第 i 个舱室的总开销包含三部分· 开启联合屏障的花费union[j]。· 针对“既没有与左边联合也没有与右边联合”的时刻开启单独屏障的花费需要单独屏障的时刻集合 (所有时刻补集 ^ j) rain[i]其花费为 single[该集合]。· 注意第 i 个舱室被左边联合屏障保护的时刻 pre 不需要再付任何费用。Java实现代码javaclass Solution {public int defendSpaceCity(int[] time, int[] position) {int maxPos 0, maxTime 0;for (int t : time) maxTime Math.max(maxTime, t);for (int p : position) maxPos Math.max(maxPos, p);int m 1 maxTime; // 状态总数因为time最大为5所以m最大为32int[] rain new int[maxPos 1];for (int i 0; i time.length; i) {// 将时刻映射到二进制的第 (time[i]-1) 位rain[position[i]] | 1 (time[i] - 1);}// 1. 预处理单屏障和联合屏障的代价int[] single new int[m];int[] union new int[m];for (int i 1; i m; i) {int lb i -i; // 最低位的1int j i ^ lb; // 去掉最低位的1int lb2 j -j; // 前一个状态的连续段// 判断这个新加的1时刻是否与原有最右侧时刻相邻boolean isAdjacent (lb (lb2 1));// 单独屏障首次开需要2维持需要1single[i] single[j] (isAdjacent ? 1 : 2);// 联合屏障首次开需要3维持需要1union[i] union[j] (isAdjacent ? 1 : 3);}// 2. DPint INF Integer.MAX_VALUE / 2;int[][] dp new int[maxPos 2][m];for (int i 0; i maxPos 1; i) {Arrays.fill(dp[i], INF);}// 初始化第0个舱室它没有左边的舱室所以 pre 只能是 0for (int j 0; j m; j) {// 第0个舱室不能与左边联合所以它的花费只有自己开联合 针对剩余时刻开单屏障int mask (m - 1) ^ j; // 所有时刻中没有与右边联合的时刻集合int needSingle mask rain[0];dp[0][j] union[j] single[needSingle];}// 遍历从1到maxPos的每个舱室for (int i 1; i maxPos; i) {for (int j 0; j m; j) {// 枚举上一个舱室 i-1 的联合屏障集合 pre// pre 必须是 j 的补集的子集即 (pre j) 0int mask (m - 1) ^ j;for (int pre mask; ; pre (pre - 1) mask) {// 计算当前舱室 i 需要单独屏障的时刻// 这些时刻是既没有与左边联合(pre)也没有与右边联合(j)并且有陨石int needSingle (mask ^ pre) rain[i];int cost dp[i - 1][pre] union[j] single[needSingle];dp[i][j] Math.min(dp[i][j], cost);if (pre 0) break;}}}// 答案最后一个舱室之后没有舱室了所以它不能与右边联合状态j必须为0// 但我们的dp定义是第i个舱室与i1联合所以需要再处理一个虚拟舱室强制其j0// 或者直接取 dp[maxPos][0]因为最后一个舱室的右边没有舱室状态必须为0// 更严谨的写法是再做一个虚拟舱室的转移int ans INF;for (int pre 0; pre m; pre) {// 虚拟位置 maxPos 1没有陨石且联合状态 j 必须为 0int needSingle ((m - 1) ^ pre) 0; // 无陨石ans Math.min(ans, dp[maxPos][pre] single[0]);}return ans;}} DeepSeek LeetCode LCP 53. 守护太空城 Java实现
实现这道题的核心思路是利用状态压缩动态规划。因为 time[i] 最大只有 5所以可以用一个 5 位的二进制数来表示某个舱室在 5 个时刻的屏障开启情况。问题的难点在于处理相邻舱室的联合屏障我们可以通过枚举上一个舱室在哪些时刻开启了联合屏障来解决。以下是详细解析和可直接运行的Java代码。解题思路1. 数据表示用 rain[p] 的二进制低5位表示位置 p 在哪些时刻有陨石。第 t 时刻有陨石则第 t 位从0开始为1。2. 预处理代价对于任意一个状态 j二进制表示哪些时刻有屏障计算单独开启这些屏障所需的最小能量 single[j]。如果同一个舱室在两个相邻时刻都需要屏障则第二个时刻只需花 1 点能量维持即可否则需要花 2 点能量重新开启。3. 核心DPdp[i][j] 表示处理到第 i 个舱室且第 i 个舱室与第 i1 个舱室在时刻集合 j 开启联合屏障时的最小总能量。· 当计算 dp[i][j] 时枚举上一个舱室 i-1 的联合屏障时刻集合 pre。注意 pre 和 j 不能有交集因为一个时刻一个舱室不能被两个屏障覆盖。· 状态转移方程dp[i][j] min(dp[i-1][pre] cost)。· 这个 cost 是第 i 个舱室的总开销包含三部分· 开启联合屏障的花费union[j]。· 针对“既没有与左边联合也没有与右边联合”的时刻开启单独屏障的花费需要单独屏障的时刻集合 (所有时刻补集 ^ j) rain[i]其花费为 single[该集合]。· 注意第 i 个舱室被左边联合屏障保护的时刻 pre 不需要再付任何费用。Java实现代码javaclass Solution {public int defendSpaceCity(int[] time, int[] position) {int maxPos 0, maxTime 0;for (int t : time) maxTime Math.max(maxTime, t);for (int p : position) maxPos Math.max(maxPos, p);int m 1 maxTime; // 状态总数因为time最大为5所以m最大为32int[] rain new int[maxPos 1];for (int i 0; i time.length; i) {// 将时刻映射到二进制的第 (time[i]-1) 位rain[position[i]] | 1 (time[i] - 1);}// 1. 预处理单屏障和联合屏障的代价int[] single new int[m];int[] union new int[m];for (int i 1; i m; i) {int lb i -i; // 最低位的1int j i ^ lb; // 去掉最低位的1int lb2 j -j; // 前一个状态的连续段// 判断这个新加的1时刻是否与原有最右侧时刻相邻boolean isAdjacent (lb (lb2 1));// 单独屏障首次开需要2维持需要1single[i] single[j] (isAdjacent ? 1 : 2);// 联合屏障首次开需要3维持需要1union[i] union[j] (isAdjacent ? 1 : 3);}// 2. DPint INF Integer.MAX_VALUE / 2;int[][] dp new int[maxPos 2][m];for (int i 0; i maxPos 1; i) {Arrays.fill(dp[i], INF);}// 初始化第0个舱室它没有左边的舱室所以 pre 只能是 0for (int j 0; j m; j) {// 第0个舱室不能与左边联合所以它的花费只有自己开联合 针对剩余时刻开单屏障int mask (m - 1) ^ j; // 所有时刻中没有与右边联合的时刻集合int needSingle mask rain[0];dp[0][j] union[j] single[needSingle];}// 遍历从1到maxPos的每个舱室for (int i 1; i maxPos; i) {for (int j 0; j m; j) {// 枚举上一个舱室 i-1 的联合屏障集合 pre// pre 必须是 j 的补集的子集即 (pre j) 0int mask (m - 1) ^ j;for (int pre mask; ; pre (pre - 1) mask) {// 计算当前舱室 i 需要单独屏障的时刻// 这些时刻是既没有与左边联合(pre)也没有与右边联合(j)并且有陨石int needSingle (mask ^ pre) rain[i];int cost dp[i - 1][pre] union[j] single[needSingle];dp[i][j] Math.min(dp[i][j], cost);if (pre 0) break;}}}// 答案最后一个舱室之后没有舱室了所以它不能与右边联合状态j必须为0// 但我们的dp定义是第i个舱室与i1联合所以需要再处理一个虚拟舱室强制其j0// 或者直接取 dp[maxPos][0]因为最后一个舱室的右边没有舱室状态必须为0// 更严谨的写法是再做一个虚拟舱室的转移int ans INF;for (int pre 0; pre m; pre) {// 虚拟位置 maxPos 1没有陨石且联合状态 j 必须为 0int needSingle ((m - 1) ^ pre) 0; // 无陨石ans Math.min(ans, dp[maxPos][pre] single[0]);}return ans;}}