The 2023 Guangdong Provincial Collegiate Programming Contest

https://codeforces.com/gym/104369

B. Base Station Construction

题意

现在需要在点 $1,2,\cdots,n$ 上建设基站，在点 $i$ 建设基站的费用为 $a_i$。有 $m$ 个要求，每个要求为区间 $[l_i,r_i]$ 内至少有一个基站。问最小费用是多少。

题解

如果每个点的费用一样，那这是个经典的贪心问题。但是由于费用不同，显然无法贪心，考虑使用dp。

设 $f_i$ 表示前 $i$ 个位置且第 $i$ 个位置必须建设基站的最小总成本。考虑上一个建设基站的位置 $j$，有转移

$$f_i=\min_{j} f_j+a_i$$

考虑这些限制，就是 $[j+1,i-1]$ 不能包含一个要求的区间，所以，对于每个 $i$ 我们可以预处理出最小的 $p_i$，满足 $[p_i,i]$ 不包含一个要求的区间，这可以用双指针处理。

上面的dp可以利用单调队列优化。以前写的单调队列优化dp似乎总有这样那样的问题，这次抄了一份std，希望可以一直用。

还有一个小技巧是，为了统计最终答案，我们可以令 $a_{n+1}=0$，然后要求 $[n+1,n+1]$ 必须有一个基站，这样答案就是 $f_{n+1}$。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+5;
int a[N],p[N],q[N];
ll f[N];
vector<int> b[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int _;cin>>_;
    while(_--)
    {
        int n;cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        a[++n]=0;
        for(int i=1;i<=n;i++) b[i].clear();
        int m;cin>>m;
        while(m--)
        {
            int l,r;cin>>l>>r;
            b[l].push_back(-r),b[r].push_back(l);
        }
        b[n].push_back(-n);b[n].push_back(n);
        int cur=0;
        for(int i=1,j=1;j<=n;j++)
        {
            for(int x:b[j]) 
                if(x>0&&x>=i) cur++;
            while(cur>0&&i<=j)
            {
                for(int x:b[i])
                    if(x<0&&-x<=j) cur--;
                i++;
            }
            p[j]=i;
        }
        f[0]=0,f[1]=a[1];
        int h=1,t=1;
        q[t++]=0,q[t++]=1;
        for(int i=2;i<=n;i++)
        {
            int lim=p[i-1]-1;
            while(q[h]<lim) h++;
            f[i]=f[q[h]]+a[i];
            while(h<t&&f[i]<=f[q[t-1]]) t--;
            q[t++]=i;
        }
        cout<<f[n]<<'\n';
    }
    return 0;
}