题解：P9691 [GDCPC 2023] Base Station Construction

· · 题解

思路

First

一眼 DP。

Second

设 dp_i 表示对于前 i 个位置，选择第 i 个位置的答案最小值。

考虑如何转移。

可以想象转移方程的样子大概是 dp_i = \min_{j=Left_i}^{Right_i} dp_j + a_i，且显然 Right_i = i-1。

所以接下来的任务是对于每个 i，找到可以往 i 转移的下界。

考虑什么样的 j 可以向 i 转移。显然当且仅当不存在 k \in [1,m]，使得 j < L_k \le R_k < i。

即对于所有的 k，R_k < i，有 j \ge \max L_k。

所以 Left_i = \max L_k，其中 R_k < i。

这样 DP 方程就结束了。

此时复杂度 O(n^2)。

Third

本题重点——单调队列优化 DP，来了！

不会单调队列的不妨看一下这个题。

然后就没有然后了。

思考单调队列过程时，现在在点 i。

如果 q.front()<Left[i]，就 q.pop()。

然后转移，最后加入 i。

最终复杂度 O(n)。

Last

这时候有人就问了：所以最终状态是什么呢？

这里比较巧妙，在给定的 n 个点后新建一个点，权值为 0（即 a_{n+1} = 0）。

最终答案就是 dp_{n+1}。

最终有一些不可缺少的东西。

#include<bits/stdc++.h>
#define int long long
using namespace std;
bool Beginning;

#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define se second
#define fi first
using PII=pair<int,int>;
using PIB=pair<int,bool>;
using PBI=pair<bool,int>;
using PBB=pair<bool,bool>;
using PDI=pair<double,int>;
using PID=pair<int,double>;

namespace Memory_Love{
    int read(){ int x=0; bool flag=1; char ch=getchar();
        while(ch<'0' || ch>'9'){if(ch=='-') flag=0;ch=getchar();}
        while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
        return flag? x:-x;}
    void write(int x,char ch=0){if(x<0) x=-x,putchar('-');
        static short s[35],top=-1; do{s[++top]=x%10;x/=10;}while(x);
        while(~top) putchar(s[top--]+48); if(ch) putchar(ch);}
    int gcd(int a,int b){return b==0? a:gcd(b,a%b);}
    int lcm(int a,int b){return a/gcd(a,b)*b;}
} using namespace Memory_Love;
const int N=5e5+5;
int n,m;
int a[N],L[N],R[N];

namespace DP
{
    int last[N],dp[N];
    deque<int> q;
    void init()
    {
        int i; a[++n]=0;
        while(q.size()) q.pop_back();
        for(i=1;i<=n;i++) last[i]=0;
        for(i=1;i<=m;i++) last[R[i]+1]=max(last[R[i]+1],L[i]);
        for(i=1;i<=n;i++) last[i]=max(last[i],last[i-1]);
    }
    int solve()
    {
        int i;
        q.push_back(0);
        for(i=1;i<=n;i++)
        {
            while(q.size() && q.front()<last[i])
            q.pop_front();
            dp[i]=dp[q.front()]+a[i];
            while(q.size() && dp[q.back()]>dp[i])
            q.pop_back();
            q.push_back(i);
        }
        return dp[n];
    }
}

int solve()
{
    int i;
    n=read();   for(i=1;i<=n;i++) a[i]=read();
    m=read();   for(i=1;i<=m;i++) L[i]=read(),R[i]=read();
    DP::init(); return DP::solve();
}

bool Ending;
signed main()
{
    int T=read(); while(T--) write(solve(),'\n');
    cerr<<"\nused:"<<(abs(&Ending-&Beginning)/1048576)<<"MB\n";
    return 0;
}