自动搬运

查看原文

来自洛谷，原作者为

	DaiRuiChen007 白鸟白鸟 不要回头望 你要替我飞去那地方 一去那地方 那是你我共同故乡

搬运于2025-08-24 22:47:15，当前版本为作者最后更新于2023-06-12 16:48:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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;
}