P9312 题解

· · 题解

P9312 题解

Problem Link

题目大意

平面直角坐标系上有 n 个点，坐标为 (1,h_1)\sim (n,h_n)，保证 h 是一个 1\sim n 的排列，对于横坐标相邻的点有线段连接，你的目标是沿着连接相邻两个点的线段遍历这 n 个点。

有 m 个区间，第 i 个区间 [l_i,r_i] 有价格 w_i，需要在 p_i 上购买，你能从 h_i 移动到 h_{i+1} 当且仅当 [h_i,h_{i+1}] 中的每个 x 都至少被一个你购买的区间覆盖。

对于每个区间 [l_i,r_i] 求出：你购买 [l_i,r_i] 后从 p_i 开始遍历所有点的最小花费。

数据范围：n,m\le 2000。

思路分析

考虑 dp 状态：dp_{\mathbf S,i} 表示购买的线段覆盖了 \mathbf S，且当前位置在 i 时继续遍历所有点的最小花费，容易发现知道 \mathbf S 和 i 就可以知道 i 能到达的整个区间，枚举下一步购买的线段即可。

注意到一个观察：对于一个横坐标的区间 [l,r]，想要拓展到 (l,h_l)\sim (r,h_r) 中的所有点需要的 \mathbf S 一定是一个包含 [\min h_{l\sim r},\max h_{l\sim r}\}] 的连续区间 [L,R]，而剩余的线段可以在以后需要拓展时再购买，因此可以用 dp_{L,R,i} 表示状态。

考虑进一步简化状态，注意到当我们确定覆盖区间 [L,R] 后，能够拓展的横坐标区间 [l,r] 可能有很多个不相交的段，因此我们需要记录一维 i 表示我们实际所在的是哪个段。

而注意到 L 一定是某个最小的 l_u，R 一定是某个最大的 r_v，因此当我们记录 u,v 后，横坐标区间 [l,r] 一定经过 p_u,p_v，那么这样的 [l,r] 就是唯一的，此时只需要记录状态 dp_{u,v} 即可。

考虑转移的形式：

\begin{aligned} dp_{u,v}&\gets \min_{r_v<r_{v'}}\{dp_{u,v'}+w_{v'}\}\\ dp_{u,v}&\gets \min_{l_{u'}<l_u}\{dp_{u',v}+w_{u'}\}\\ dp_{u,v}&\gets \min_{l_k<l_u,r_v<r_k}\{dp_{k,k}+w_k\} \end{aligned}

即新购买的线段分别更新了左端点 / 右端点 / 同时更新 [l_u,r_v]。

考虑优化第一个转移，注意到一个结论：若 r_i<r_j<r_k，且 k 不能被 dp_{u,j} 购买，那么 k 一定不能被 dp_{u,i} 购买，因为 [l_u,r_i]\subseteq [l_u,r_j]，且表示的区间都包含 p_u，那么 dp_{u,i} 对应的区间 \mathbf I 一定包含 dp_{u,j} 对应的的区间 \mathbf J，若 p_k\not\in \mathbf I 则 p_k 一定不属于 \mathbf J。

因此我们对于一个确定的 u，对 v 按 r_v 从大到小排序处理，用小根堆维护最小的 dp_{u,v'}+w_{v'}，若当前的 p_{v'} 无法到达则直接弹出，根据我们刚才的结论，dp_{u,v'} 一定不可能更新 r_v 更小的状态。

对于第二种转移同理，我们对每个确定的 v 按 l_u 从小到大转移，分别维护小根堆即可。

考虑第三种转移：dp_{k,k}\to dp_{u,v} 的过程，考虑用前两种转移来描述：dp_{k,k}\to dp_{k,v}\to dp_{u,v}，但问题是状态 dp_{k,v} 是不合法状态（l_k<l_v），为了让这种转移可以被前两种转移刻画，我们定义这样的 dp_{k,v} 为合法状态且值恰好是 dp_{k,k} 即可。

按 l_u 从小到大枚举 u，按 r_v 从大到小枚举 v，维护 2m 个小根堆分别处理 u,v 一定时的两种转移即可。

时间复杂度：\mathcal O(m^2\log m)。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2001,INF=2e9;
int h[MAXN],L[MAXN],R[MAXN],P[MAXN],W[MAXN];
int dp[MAXN][MAXN]; //lanterns covered L[l]~R[r]
int lb[MAXN][2],rb[MAXN][2]; //section >=L[i], section <=R[i]
priority_queue <array<int,2>,vector<array<int,2>>,greater<array<int,2>>> Ql[MAXN],Qr[MAXN];
//best strategy when fix lp/rp
signed main() {
    freopen("code.in","r",stdin);
    freopen("code.out","w",stdout);
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) scanf("%d",&h[i]);
    for(int i=1;i<=m;++i) scanf("%d%d%d%d",&P[i],&W[i],&L[i],&R[i]);
    vector <int> ordL(m),ordR(m);
    iota(ordL.begin(),ordL.end(),1);
    sort(ordL.begin(),ordL.end(),[&](int x,int y){ return L[x]<L[y]; });
    iota(ordR.begin(),ordR.end(),1);
    sort(ordR.begin(),ordR.end(),[&](int x,int y){ return R[x]>R[y]; });
    for(int i=1;i<=m;++i) {
        for(int &p=lb[i][0]=P[i]+1;p>1&&h[p-1]>=L[i];--p);
        for(int &p=lb[i][1]=P[i]-1;p<n&&h[p+1]>=L[i];++p);
        for(int &p=rb[i][0]=P[i]+1;p>1&&h[p-1]<=R[i];--p);
        for(int &p=rb[i][1]=P[i]-1;p<n&&h[p+1]<=R[i];++p);
    }
    for(int i:ordL) for(int j:ordR) {
        dp[i][j]=INF;
        int l=max(lb[i][0],rb[j][0]),r=min(lb[i][1],rb[j][1]);
        if(P[i]<l||P[i]>r||P[j]<l||P[j]>r||(R[j]<R[i]&&L[i]>L[j])) continue;
        if(l==1&&r==n) dp[i][j]=0;
        else if(R[j]<R[i]) dp[i][j]=dp[i][i];
        else if(L[i]>L[j]) dp[i][j]=dp[j][j];
        else {
            auto gval=[&](auto &Q,int il,int ir,int hl,int hr) {
                while(!Q.empty()) {
                    int idx=Q.top()[1];
                    if(P[idx]<il||P[idx]>ir||R[idx]<hl||L[idx]>hr) Q.pop();
                    else return Q.top()[0];
                }
                return INF;
            };
            dp[i][j]=min(dp[i][j],gval(Ql[i],l,r,L[i],R[j]));
            dp[i][j]=min(dp[i][j],gval(Qr[j],l,r,L[i],R[j]));
        }
        if(dp[i][j]<INF) Ql[i].push({dp[i][j]+W[j],j}),Qr[j].push({dp[i][j]+W[i],i});
    }
    for(int i=1;i<=m;++i) {
        if(dp[i][i]<INF) printf("%d\n",dp[i][i]+W[i]);
        else puts("-1");
    }
    return 0;
}