P9691 [GDCPC 2023] Base Station Construction题解

直接枚举会超时，注意到 pre[i] 是单调不减的，因此可以用单调队列维护 dp[j] 的最小值。

单调队列优化

• 使用双端队列 dq 存储下标 j，保证队列中 dp[j] 单调递增。
• 对于每个 i：
  1. 弹出队首所有 < pre[i] 的下标（它们不再可用）。
  2. 此时队首下标对应的 dp 值即为最小，计算 dp[i] = dp[dq.front()] + a[i]。
  3. 将 i 加入队尾，并弹出队尾中 dp 值 ≥ dp[i] 的下标（保持单调性）。

最后 dp[n+1] 即为答案（因为虚拟点成本为 0，它不会增加总成本，但帮助我们统一处理）。

复杂度分析

• 预处理 pre 数组：O(n + m)
• 动态规划：每个位置进出队列一次，O(n)
• 总复杂度：O(n + m)，满足题目要求。

代码实现

#include <bits/stdc++.h>
using ll = long long;
using namespace std;
const ll N = 5e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;void solve() {int n;cin >> n;vector<ll> a(n + 2);for (int i = 1; i <= n; i++)cin >> a[i];a[++n] = 0; // 添加虚拟点vector<ll> pre(n + 2, 0); // pre[i] 表示所有右端点 < i 的区间的左端点最大值int m;cin >> m;for (int i = 1; i <= m; i++) {int l, r;cin >> l >> r;// 要求 r+1 之前必须有一个基站位于 ≥ l 的位置pre[r + 1] = max(pre[r + 1], (ll)l);}pre[1] = 0; // 左端点最大值为0for (int i = 2; i <= n; i++) {pre[i] = max(pre[i], pre[i - 1]);} // 前缀最大值vector<ll> dp(n + 1, 0); // dp[i] 表示在 i 处建站deque<int> dq;dq.push_back(0);for (int i = 1; i <= n; i++) {// 弹出队首所有小于 pre[i] 的下标（不再能作为上一个基站的位置）while (!dq.empty() && dq.front() < pre[i])dq.pop_front();// 队首 dp 值最小，转移得到 dp[i]dp[i] = dp[dq.front()] + a[i];while (!dq.empty() && dp[dq.back()] >= dp[i])dq.pop_back();dq.push_back(i);}cout << dp[n] << '\n';
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin >> T;while (T--)solve();return 0;
}