EGOI2021 Lanterns / 灯笼

本文主要是介绍EGOI2021 Lanterns / 灯笼，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

洛谷P9312 [EGOI2021] Lanterns / 灯笼

题目大意

有 $n$ 座山脉，这些山脉可以用平面直角坐标系上的 $n$ 个点表示，我们称这些点为山峰。第 $i$ 座山峰的坐标为 $i,h_i)$ ， $h_i$ 表示第 $i$ 座山峰的海拔高度，保证 $h_1,h_2,\dots,h_n$ 构成一个 $1\sim n$ 的排列。

山峰 $i$ 和山峰 $i + 1$ 用一条线段相连。

约翰要携带至少一盏正常工作的灯笼才能上山。有 $k$ 盏灯笼可以购买，第 $j$ 盏灯笼可以在山峰 $p_j$ 上以 $c_j$ 法郎的价格购买。

然而，第 $j$ 盏灯笼只有约翰的海拔在 $a_j,b_j]$ 时才能正常工作，否则就会停止工作，在回到对应海拔上才会恢复正常工作。

如果现在约翰在山峰 $p$ ，他可以执行以下三种操作之一：

购买一个山峰 $p$ 上售卖的灯笼
如果 $p > 1$ ，他可以走到山峰 $p - 1$
如果 $p < n$ ，他可以走到山峰 $p + 1$

约翰在没有正常工作的灯笼时不能移动。他必须保证每个时刻都有至少一盏灯笼正常工作，才能在两座山峰间移动。（在行走过程中不必是同一盏灯笼。）

对于每一个 $1\leq p\leq n$ ，求约翰一开始在山峰 $p$ 上时，他至少要花费多少法郎的价格才能走遍所有山脉。

$1\leq n,k\leq 2\times 10^3$

时间限制 $3000 m s$ ，空间限制 $1024 MB$ 。

题解

首先，我们知道，约翰购买的灯笼要是连续的，因为如果不连续的话，就会有一些地方走不到。如果这些地方不需要走的话，就不是最优的。那么，我们只需要记录所有所有已购买的灯笼中最小的 $a$ 值 $a_i$ 和最大的 $b$ 值 $b_j$ ，即可知道当前所有已购买的灯笼构成的区间。

设 $f_{l,r,v}$ 表示当前在第 $v$ 座山峰，灯笼构成的区间为 $[l, r]$ ，继续探索完所有山峰至少需要花费的价格。因为能够构成一个区间 $[l, r]$ 的横坐标有多段，所以要记录一个 $v$ 来表示当前在那一段。

我们发现， $f_{l,r,v}$ 中的 $l$ 一定是当前购买的灯笼中 $a$ 值最小的， $r$ 一定是当前购买的灯笼中 $b$ 值最大的。设 $a$ 值最小的为 $a_i$ ， $b$ 值最小的为 $b_j$ ，那么如果用 $i$ 和 $j$ 来表示一个状态，那么构成 $a_i,b_j]$ 的横坐标段一定经过 $p_i$ 和 $p_j$ ，这样就能确定其所在的横坐标段。所以我们不在需要记录当前所在的山峰 $v$ ，只需要记录状态 $f_{i,j}$ 即可。

那么，转移式为

$\begin{aligned} f_{i,j}&\leftarrow \min\limits_{r_j\leq r_t}\{f_{i,t}+w_t\} \\ f_{i,j}&\leftarrow \min\limits_{l_t<l_i}\{f_{t,j}+w_t\} \\ f_{i,j}&\leftarrow \min\limits_{l_t<l_i,r_j<r_t}\{f_{t,t}+w_t\} \end{aligned}$

其中， $t$ 需要满足 $l_i\leq t\leq r_j$ 。

在枚举 $i, j$ 的时候，我们要按 $l_i$ 从小到大枚举 $i$ ，按 $r_j$ 从大到小枚举 $j$ 。

这样转移的时间复杂度是 $O(n^3)$ 的，我们考虑优化。

对于第一种转移，我们注意到：当 $r_i<r_j<r_t$ ，且 $t$ 不能被 $f_{h,j}$ 购买，则 $t$ 不能被 $f_{h,i}$ 购买。那么，我们可以维护 $k$ 个小根堆，第 $i$ 个小根堆 $ql_i$ 存储 $f_{i,t}+w_t$ 。在查询的时候，如果堆顶的 $p_t$ 无法到达，则将其弹出，否则就用其更新当前的 $f$ 值。

对于第二种转移，与第一种转移类似，用 $k$ 个小根堆，第 $j$ 个小根堆 $qr_j$ 存储 $f_{t,j}+w_t$ ，和上面一样处理即可。

对于第三种转移， $f_{t,t} \rightarrow f_{i,j}$ 的过程可以看作用上面两种转移来描述： $f_{t,t} \rightarrow f_{t,j} \rightarrow f_{i,j}$ 。不过， $f_{t,j}$ 是不合法状态（ $r_t>r_j$ ），于是我们定义这样的 $f_{t,j}$ 为合法状态，并且其值为 $f_{t,t}$ ，这样我们就能让这种转移在前两种转移中体现。

时间复杂度为 $O(k^2\log k)$ 。

code

#include<bits/stdc++.h>
using namespace std;
const int N=2000,inf=2100000000;
int n,k,h[N+5],p[N+5],w[N+5],a[N+5],b[N+5];
int dpl[N+5],dpr[N+5],vl[N+5][2],vr[N+5][2],f[N+5][N+5];
bool cmp1(int x,int y){return a[x]<a[y];}
bool cmp2(int x,int y){return b[x]>b[y];}
struct node{int x,id;friend bool operator<(node ax,node bx){return ax.x>bx.x;}
};
priority_queue<node>ql[N+5],qr[N+5];
int gtval(priority_queue<node>&q,int l,int r,int hl,int hr){while(!q.empty()){int tp=q.top().id;if(p[tp]<l||p[tp]>r||b[tp]<hl||a[tp]>hr) q.pop();else return q.top().x;}return inf;
}
int main()
{scanf("%d%d",&n,&k);for(int i=1;i<=n;i++) scanf("%d",&h[i]);for(int i=1;i<=k;i++){scanf("%d%d%d%d",&p[i],&w[i],&a[i],&b[i]);dpl[i]=dpr[i]=i;}sort(dpl+1,dpl+k+1,cmp1);sort(dpr+1,dpr+k+1,cmp2);for(int i=1;i<=k;i++){for(int &j=vl[i][0]=p[i]+1;j-1>=1&&h[j-1]>=a[i];--j);for(int &j=vl[i][1]=p[i]-1;j+1<=n&&h[j+1]>=a[i];++j);for(int &j=vr[i][0]=p[i]+1;j-1>=1&&h[j-1]<=b[i];--j);for(int &j=vr[i][1]=p[i]-1;j+1<=n&&h[j+1]<=b[i];++j);}for(int w1=1;w1<=k;w1++){for(int w2=1;w2<=k;w2++){int i=dpl[w1],j=dpr[w2];f[i][j]=inf;int l=max(vl[i][0],vr[j][0]),r=min(vl[i][1],vr[j][1]);if(p[i]<l||p[i]>r||p[j]<l||p[j]>r||(a[j]<a[i]&&b[j]<b[i])) continue;if(l==1&&r==n) f[i][j]=0;else if(a[j]<a[i]) f[i][j]=f[j][j];else if(b[j]<b[i]) f[i][j]=f[i][i];else{f[i][j]=min(f[i][j],gtval(ql[i],l,r,a[i],b[j]));f[i][j]=min(f[i][j],gtval(qr[j],l,r,a[i],b[j]));}ql[i].push((node){f[i][j]+w[j],j});qr[j].push((node){f[i][j]+w[i],i});}}for(int i=1;i<=k;i++){if(f[i][i]<inf) printf("%lld\n",f[i][i]+w[i]);else printf("-1\n");}return 0;
}