自动搬运

查看原文

来自洛谷，原作者为

	sunzz3183 AFOed

搬运于2025-08-24 22:50:50，当前版本为作者最后更新于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;
}