P9691 [GDCPC2023] Base Station Construction 题解

sunzz3183 · 2023-12-01 19:10:54 · 题解

P9691 [GDCPC2023] Base Station Construction 题解

题意

给定一个长度为 n 的序列 a，现在需要选择任意个数，使得选择的数的和最小且对于给定给的 m 个区间 [l_i,r_i]，每个区间都有至少一个数被选择。

分析

设状态 f_i 为考虑了前 i 个数，并且第 i 个数一定选的最小值。

我们可以把 a_{n+1}=0 ，这样 f_{n+1} 就是答案。

转移类似这样：

其中，转移需要满足 m 个条件，考虑，对于每一个合法的 j，说明 (j,i) 的区间内，没有一个完整的区间，所以我们记录一个数组 pre，pre_i 表示能转移到 i 的最小合法的 j。

所以完整转移为：

然后求 pre 的方式为：

两个式子分别可以用单调队列优化 dp 和预处理前缀最大值求出来。

代码

void Main(){
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    a[++n]=0;
    for(int i=1;i<=n;i++)pre[i]=0;
    m=read();
    for(int i=1;i<=m;i++){
        int l=read(),r=read();
        pre[r+1]=max(pre[r+1],l);
    }
    pre[1]=0;
    for(int i=2;i<=n;i++)pre[i]=max(pre[i],pre[i-1]);
    l=1,r=0;q[++r]=0;
    for(int i=1;i<=n;i++){
        while(l<=r&&q[l]<pre[i])l++;
        f[i]=f[q[l]]+a[i];
        while(l<=r&&f[q[r]]>=f[i])r--;
        q[++r]=i;
    }
    printf("%lld\n",f[n]);
    return;
}