C++实现烟花DP单调队列优化算法详解

这道题是一个**动态规划**问题，需要用**单调队列优化**来处理大范围状态转移，否则会超时。 ## 🧠 题目分析 **核心思路：** - 有 m 个烟花，每个烟花在时间 tᵢ 在位置 aᵢ 发射 - 你在某个时间只能在一个位置，且一个单位时间最多移动 d 个位置 - 每个烟花给你幸福值 = bᵢ - |aᵢ - x|（x 是你当前位置） - 需要在时间 t 时选择最优位置，使得总幸福值最大 **暴力思考：** - 如果 m 个烟花，每个烟花有 n 个可能位置，那状态数太多，不可行 **动态规划定义：** - 设 dp[i][x] 表示看完第 i 个烟花后，你恰好处于位置 x 时能获得的最大幸福值 - 转移公式： ``` dp[i][x] = max(dp[i-1][y] + b[i] - |a[i] - x|) 其中 |y - x| <= (t[i] - t[i-1]) * d ``` 思路很清晰，但直接算复杂度太高：O(m × n²)，n 高达 150000，完全不可行。 --- ## ✨ 动态规划优化思路 推一下公式： ``` dp[i][x] = b[i] - |a[i] - x| + max(dp[i-1][y]) 其中 y 在 [x - k, x + k] 之间，k = (t[i] - t[i-1]) * d ``` 这时，问题转化为：**求某个滑动窗口 [x-k, x+k] 内的最大值**。 这就是经典的**单调队列优化DP**问题。 - 我们可以先从左到右扫描 x，维护一个单调递减队列，得到窗口最大值 - 然后从右到左再扫一遍，取两边最大值 --- ## 💻 C++ 完整代码 ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = -1e18; // 极小值 int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; ll d; cin >> n >> m >> d; vector<ll> dp(n + 1, 0); // dp[x] 表示当前烟花之后，在位置x的最大幸福值 ll lastTime = 1; // 初始时间 for (int i = 0; i < m; i++) { ll a, b, t; cin >> a >> b >> t; // 可移动距离 ll moveDist = (t - lastTime) * d; lastTime = t; // 单调队列优化 deque<int> dq; // 存下标 vector<ll> newdp(n + 1, INF); // 从左到右滑动窗口，求窗口最大值 // 区间 [x - moveDist, x + moveDist] // 先处理右边界 for (int x = 1; x <= n; x++) { // 添加新位置到队列 while (!dq.empty() && dp[dq.back()] <= dp[x]) dq.pop_back(); dq.push_back(x); // 移除过期的队首（超出左边界） ll left = x - moveDist; while (!dq.empty() && dq.front() < left) dq.pop_front(); // 当前可用最大值 if (!dq.empty()) { ll maxPrev = dp[dq.front()]; newdp[x] = max(newdp[x], maxPrev); } } // 从右到左，处理左边界（窗口左边的位置） dq.clear(); for (int x = n; x >= 1; x--) { // 添加新位置 while (!dq.empty() && dp[dq.back()] <= dp[x]) dq.pop_back(); dq.push_back(x); // 移除过期的队首（超出右边界） ll right = x + moveDist; while (!dq.empty() && dq.front() > right) dq.pop_front(); if (!dq.empty()) { ll maxPrev = dp[dq.front()]; newdp[x] = max(newdp[x], maxPrev); } } // 加上本烟花的幸福值 for (int x = 1; x <= n; x++) { if (newdp[x] > INF/2) { dp[x] = newdp[x] + b - abs(a - x); } else { dp[x] = INF; } } } // 结果取最大值 ll ans = INF; for (int x = 1; x <= n; x++) { ans = max(ans, dp[x]); } cout << ans << "\n"; return 0; } ``` --- ## ⚙️ 代码解释 | 部分 | 说明 | |------|------| | **dp 数组** | 存看完前 i 个烟花后每个位置的最大幸福值 | | **moveDist** | 两次烟花之间能移动的最大距离 = (tᵢ - tᵢ₋₁) × d | | **单调队列** | 维护窗口内 dp 最大值，时间复杂度降为 O(n) | | **两次扫描** | 一次从左到右覆盖窗口左半，一次从右到左覆盖窗口右半 | **时间复杂度：** O(m × n) ≈ 300 × 150000 = 4500 万，可以接受 **空间复杂度：** O(n) --- ## 🚨 易错点和注意事项 1. **数据范围大**：bᵢ 最大 10⁹，相加可能超过 int，必须用 `long long` 2. **初始时间从 1 开始**：第一次烟花时间 t₁ 可能远大于 1，所以要算初始可移动距离 3. **INF 要设极小值**（如 -1e18），防止溢出 4. **单调队列细节**：存的是下标，比较的是 dp 值 5. **负数幸福值**：答案是负数也不要紧，题目允许 --- ## 💡 开发与优化建议 - **警惕窗口重叠**：如果 moveDist ≥ n，窗口覆盖全区间，此时可以直接用全局最大值前缀/后缀 - **分情况讨论边界**：尤其是第一次烟花时，移动到任意位置都行 - **可读性优化**：可把单调队列封装成函数，便于复用 - **性能保障**：使用 `ios::sync_with_stdio(false)` 和 `cin.tie(nullptr)` 加速输入输出 ######[AI写代码神器 | 1509点数解答 | 2026-08-15 16:19:57]