C++实现密室护盾最小移动次数（区间覆盖动态规划）

好的，这是一个典型的**区间覆盖动态规划**问题。我们需要用C++实现一个高效解法。下面我会从**问题分析**、**状态定义**、**转移方程**、**代码实现**和**复杂度分析**几个方面详细讲解。 --- ## 🧠 问题分析 - 护盾是一个长度为 `R - L + 1` 的区间，初始位置在 `[L, R]`。 - 炮弹会依次在某个列 `t` 出现，护盾需要**覆盖**该列（即 `L' <= t <= R'`）。 - 每次移动护盾只能左移或右移**1列**，所以护盾的左右端点会同步移动。 - 我们的目标是**在依次阻挡所有炮弹**的前提下，最小化总移动步数。 **关键点**： - 护盾是**连续区间**，不能拆开，移动时左右端点一起动。 - 由于护盾长度固定，我们只需要记录**左端点的位置**即可（右端点=左端点+长度-1）。 - 炮弹是**顺序出现**的，所以这是一个**序列决策问题**，可以用DP。 --- ## 📐 状态定义 设： - `len = R - L + 1` 为护盾宽度。 - 攻击序列为 `attack[1...m]`。 - 定义 `dp[i][x]` 表示**阻挡完前 i 个炮弹后**，护盾左端点停在 `x` 位置时的**最小移动步数**。 合法左端点范围：`1 <= x <= n - len + 1`。 --- ## 🔁 转移方程 对于第 `i` 个炮弹，它出现在列 `t = attack[i]`。 护盾必须满足：`x <= t <= x + len - 1`，即： ``` t - len + 1 <= x <= t ``` **初始化**： - 阻挡第1个炮弹前，护盾初始左端点 `L0 = L`。 - 如果 `L0` 在合法区间内（即满足覆盖第1个炮弹），则 `dp[1][x] = |x - L0|`（因为要从初始位置移动到x）。 - 如果不满足覆盖，则该状态不可达（设为无穷大）。 **转移**： 对于第 `i` 个炮弹（i >= 2），从第 `i-1` 个炮弹的状态转移过来： ``` dp[i][x] = min_{prev 合法} ( dp[i-1][prev] + |x - prev| ) ``` 其中 `x` 必须满足覆盖第 `i` 个炮弹。 --- ## ⚙️ 优化思路 如果直接枚举 `prev` 和 `x`，复杂度为 O(m * n^2)，n 只有 10~20，其实可以接受。但为了更优，我们可以用**前缀最小值**优化转移。 对于固定的 `i`，`x` 的合法范围是 `[max(1, t-len+1), min(t, n-len+1)]`。 转移时： ``` dp[i][x] = min( min_{prev <= x} (dp[i-1][prev] - prev) + x, min_{prev > x} (dp[i-1][prev] + prev) - x ) ``` 分别维护左半部分和右半部分的最小值。 --- ## 💻 代码实现（C++） ```cpp #include <iostream> #include <vector> #include <algorithm> #include <climits> using namespace std; int main() { int n, L, R; cin >> n >> L >> R; int m; cin >> m; vector<int> attack(m); for (int i = 0; i < m; i++) cin >> attack[i]; int len = R - L + 1; int maxLeft = n - len + 1; // 左端点最大合法位置 const int INF = 1e9; // dp[x] 表示当前处理完某些炮弹后，左端点在x的最小步数 vector<int> dp(maxLeft + 2, INF); // 处理第一个炮弹 int t0 = attack[0]; for (int x = 1; x <= maxLeft; x++) { int right = x + len - 1; if (x <= t0 && t0 <= right) { dp[x] = abs(x - L); // 初始左端点L } } // 处理后续炮弹 for (int i = 1; i < m; i++) { int t = attack[i]; vector<int> newdp(maxLeft + 2, INF); // 计算前缀最小值数组：prefMin[x] = min_{prev <= x} (dp[prev] - prev) vector<int> prefMin(maxLeft + 2, INF); for (int x = 1; x <= maxLeft; x++) { prefMin[x] = min(prefMin[x-1], dp[x] - x); } // 后缀最小值数组：sufMin[x] = min_{prev >= x} (dp[prev] + prev) vector<int> sufMin(maxLeft + 3, INF); for (int x = maxLeft; x >= 1; x--) { sufMin[x] = min(sufMin[x+1], dp[x] + x); } // 当前x必须覆盖 t int low = max(1, t - len + 1); int high = min(t, maxLeft); if (low > high) { // 无法覆盖，但题目保证有解，所以不会再出现 continue; } for (int x = low; x <= high; x++) { // 从左边转移：prefMin[x] + x int cost1 = prefMin[x] + x; // 从右边转移：sufMin[x] - x int cost2 = sufMin[x] - x; newdp[x] = min(cost1, cost2); } dp = std::move(newdp); } // 答案是最小值 int ans = INF; for (int x = 1; x <= maxLeft; x++) ans = min(ans, dp[x]); cout << ans << endl; return 0; } ``` --- ## 📊 复杂度分析 - **时间复杂度**：O(m * n)，其中 n <= 20，m 未见限制但通常不大，可轻松通过。 - **空间复杂度**：O(n)，只用了几个长度为 `maxLeft+2` 的数组。 --- ## 🧪 测试样例验证 输入： ``` 10 1 3 3 1 3 8 ``` 过程： - 初始左端点=1，区间[1,3] - 炮弹1：t=1，已覆盖，移动0 - 炮弹2：t=3，已覆盖，移动0 - 炮弹3：t=8，需要移动护盾到[8,10]（左端点=8），从1移到8需要7步？等等，但答案是5，说明中间可能选最优路径。 实际上，最优化移动： - 第1个炮弹：位置1，护盾在[1,3]覆盖，0步。 - 第2个炮弹：位置3，护盾在[1,3]覆盖，0步。 - 第3个炮弹：位置8，我们可以选择直接把护盾右移5列到左端点6，区间[6,8]覆盖8，总移动=5。 所以输出5，与样例一致。 --- ## 💡 开发建议 - **边界条件**：注意左端点合法范围 `1 ~ n-len+1`，不要越界。 - **DP初始化**：确保第一个炮弹的状态正确计算，且后续转移时注意`low`和`high`可能不包含任何合法x的情况（但题目保证有解）。 - **优化技巧**：前缀/后缀最小值是区间DP的常用优化，可以大大减少枚举量。 - **代码可读性**：变量命名清晰，使用`INF`表示不可达，避免魔法数字。 --- ######[AI写代码神器 | 1814点数解答 | 2026-07-31 19:24:10]