题解：P9691 [GDCPC 2023] Base Station Construction
Meickol
·
·
题解
单调队列优化 DP + 贪心
本题实际上就是给定若干条线段，要求在每个给出的线段中都至少要放一个点，求最后最小总代价是多少。
如果本题每个位置建立基站的权值都相同，则为经典贪心问题中的区间选点问题。
但本题每个位置建立基站的权值可以不同，于是不能直接按区间选点问题来处理，但是依然可以借助贪心思想。
考虑贪心：对于数轴中每个位置 i，用 pre_i 记录这个位置前面距离位置 i 最近的上一个线段的左端点 j，即使得 (j,i) 这段范围内不存在完整的线段，这样 [j,i] 这段区间就是就是必须要放的点的区间了，并且在这个区间内放一个点就尽可能多地覆盖给定的线段。
由于数轴中的位置值域不大，可以考虑 DP，并且由于存在多个上述的区间，需要考虑对于区间之间的转移，其实分析一下就会发现是一个单调队列优化 DP。
设 $f_i$ 表示数轴 $i$ 位置前面的必须放点的区间都已经放了且当前选择位置 $i$ 放点所需的最小总代价。
DP 转移显然：
$$
f_i = \min \{f_j\} + a_i \quad (pre_i \le j \le i-1)
$$
最终答案即为 **左端点最靠右的那条线段的左端点** 到 **右端点最靠右的那条线段的右端点** 中产生，因为在这个范围内选点一定对应整个要求的区间的点都选完了。
即：
$$
ans =\min \{ f_i \} \quad (pre_{n+1} \le i \le n)
$$
时间复杂度 $\mathcal O(n)$。
代码如下：
```cpp
#define rep(x,y,z) for(int x=y;x<=z;x++)
typedef long long LL;
const int N=5e5+5;
int n,m;
int a[N];
int q[N];
LL f[N];
int pre[N];
void solve(){
cin>>n;
rep(i,1,n) cin>>a[i];
rep(i,1,n+1) pre[i]=f[i]=0;
cin>>m;
while(m--){
int l,r;
cin>>l>>r;
pre[r+1]=max(pre[r+1],l);
}
rep(i,1,n+1) pre[i]=max(pre[i],pre[i-1]);
int hh=1,tt=0;
rep(i,1,n){
while(hh<=tt && f[q[tt]]>=f[i-1]) tt--;
q[++tt]=i-1;
while(q[hh]<pre[i]) hh++;
f[i]=f[q[hh]]+a[i];
}
LL ans;
memset(&ans,0x3f,sizeof ans);
rep(i,pre[n+1],n) ans=min(ans,f[i]);
cout<<ans;
}
```