题解 P9691 [GDCPC2023] Base Station Construction

cjh20090318 · 2024-10-30 10:09:44 · 题解

很好的单调队列优化 DP 练习题。

题意

有 i 个点排成一排，从左到右编号依次为 1 \sim n。选择第 i 个点的代价为 a_i。

有 m 个要求，第 i 个要求为在 [l_i,r_i] 中至少要选择一个节点。

请你找到代价最小的选择方案使得能够满足所有要求，并给出最小的代价。

分析

因为每个点的代价不同，所以不能直接贪心做区间选点问题，但是可以利用类似的思路。

设 f_i 表示前 i 个点中，第 i 个点必选的最小代价。

考虑转移，设转移决策点为 j，那么必然要满足的条件是对于所有右端点小于 i 的区间，j 不能小于这些区间的左端点，否则这个区间就会被漏选（因为后面的决策点也选择不了这些漏选的区间）。

设 x_i 表示右端点小于 i 的区间左端点最大值。

然后就可以写出状态转移方程：

具体实现就将所有区间按右端点从小到大排序，双指针维护最大值。因为这个决策点是单调递增的，所以可以使用单调队列优化。

最终的答案也即：

时间复杂度 O(m \log m)，瓶颈在于区间排序，动态规划部分的时间复杂度为 O(n+m)。

代码

//the code is from chenjh
#include<bits/stdc++.h>
#define MAXN 500005
using namespace std;
typedef long long LL;
int n,m,a[MAXN];
struct SEG{
    int l,r;
    bool operator < (const SEG&B)const{return r<B.r;}//将区间按右端点从小到大排序。
}e[MAXN];
LL f[MAXN];
int q[MAXN],h,t;
void solve(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    scanf("%d",&m);
    for(int i=1;i<=m;i++) scanf("%d%d",&e[i].l,&e[i].r);
    sort(e+1,e+m+1);
    int l=0;
    h=1,t=0,q[++t]=0;
    for(int i=1,j=1;i<=n;i++){
        f[i]=f[q[h]]+a[i];
        while(h<=t&&f[q[t]]>f[i]) --t;//弹出不优的决策。
        q[++t]=i;
        for(;j<=m&&e[j].r<=i;j++) l=max(l,e[j].l);//双指针维护最大值。
        while(h<=t&&q[h]<l) ++h;//排除过时决策。
    }
    printf("%lld\n",f[q[h]]);
}
int main(){
    int T;scanf("%d",&T);
    while(T--) solve();
    return 0;
}