C++高效动态规划：单调队列优化解决连续工人效率最大化问题

看到你的代码和问题描述，这个代码的时间复杂度是 O(N*K)，当 N=10^5 且 K 很大时（最坏情况 K=N），会达到 O(N^2) 导致 TLE。 ## 🤔 问题分析 当前算法对每个位置 i 都要遍历 j（1 到 K），计算所有可能的选择长度。这导致时间复杂度退化为 **O(N×K)**，在最坏情况下会超时。 ## 💡 解决方案 我们可以使用 **单调队列（Monotonic Queue）优化** DP，将时间复杂度降为 **O(N)**。 ### 🧠 核心思路 DP 状态转移方程是关键： - `dp[i]` = 前 i 个工人的最大效率 - 转移时，要么不选第 i 个工人（`dp[i-1]`），要么选择连续 j 个工人（`1 <= j <= min(K, i)`） - 选择连续 j 个时：`dp[i] = dp[i-j-1] + sum(i-j+1 到 i)` - 用前缀和表示：`dp[i] = dp[i-j-1] + prefix[i] - prefix[i-j]` **关键优化**：对于固定的 i，我们要最大化 `dp[i-j-1] - prefix[i-j]`，其中 `j ∈ [1, min(K, i)]`。令 `t = i-j`，则 `t ∈ [i-K, i-1]`。我们需要在这个区间内找到 `dp[t-1] - prefix[t]` 的最大值——这可以用**单调队列**在 O(1) 均摊时间内完成。 ### ✅ 改进后的代码 ```cpp #include <iostream> #include <vector> #include <deque> #include <algorithm> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, K; cin >> N >> K; vector<long long> efficiency(N + 1); for (int i = 1; i <= N; ++i) { cin >> efficiency[i]; } // dp[i] 表示考虑前 i 个工人的最大效率 vector<long long> dp(N + 1, 0); // 前缀和 vector<long long> prefix(N + 1, 0); for (int i = 1; i <= N; ++i) { prefix[i] = prefix[i-1] + efficiency[i]; } // value[t] = dp[t-1] - prefix[t]，用于单调队列优化 deque<int> dq; // 存储下标 // 初始化：处理第一个元素 // t=0 时，value[0] = dp[-1] - prefix[0] = 0 dq.push_back(0); for (int i = 1; i <= N; ++i) { // 移除超出窗口范围的下标（窗口大小为 K+1，因为 t 从 i-K 到 i） while (!dq.empty() && dq.front() < i - K) { dq.pop_front(); } // 当前 dp[i] 的最优选择 // 不选第 i 个工人 dp[i] = dp[i-1]; // 从单调队列中取最大值对应的 t if (!dq.empty()) { int best_t = dq.front(); // 队首是最大值 // dp[i] = dp[best_t-1] + prefix[i] - prefix[best_t] long long candidate = dp[best_t - 1] + prefix[i] - prefix[best_t]; dp[i] = max(dp[i], candidate); } // 将当前 i 加入队列（维护单调递减） long long value_i = dp[i-1] - prefix[i]; while (!dq.empty()) { int back_t = dq.back(); long long value_back = dp[back_t - 1] - prefix[back_t]; if (value_back <= value_i) { dq.pop_back(); } else { break; } } dq.push_back(i); } cout << dp[N] << endl; return 0; } ``` ### 📊 复杂度对比 | 方案 | 时间复杂度 | 空间复杂度 | |------|-----------|-----------| | 原始算法 | O(N×K) | O(N) | | 单调队列优化 | **O(N)** | O(N) | ### 🔧 关键点解释 1. **单调队列维护的变量**：我们维护 `value[t] = dp[t-1] - prefix[t]` 的单调递减队列 2. **窗口大小**：对于位置 i，合法的 t 范围为 `[i-K, i]`，所以队列中存的下标不能小于 `i-K` 3. **状态转移**：`dp[i] = max(dp[i-1], prefix[i] + max(value[t]))`，其中 `t ∈ [i-K, i-1]` ### 🔍 测试样例验证 输入： ``` 5 2 1 2 3 4 5 ``` 输出：`12`（选择工人 2,3,5 或 1,2,4,5，效率均为 12） ### 💡 开发建议 1. **使用 `ios::sync_with_stdio(false)`** 加速 C++ 输入输出 2. **注意数据类型**：效率值可能高达 10^9，N 为 10^5，总和可能超过 int 范围，务必使用 `long long` 3. **边界条件处理**：当 i-K < 0 时，窗口实际上是 [0, i]，代码中通过条件 `dq.front() < i - K` 自动处理 ######[AI写代码神器 | 1291点数解答 | 2026-08-15 16:15:28]