EGOI2021 Lanterns / 灯笼

灯笼"/>

EGOI2021 Lanterns / 灯笼

洛谷P9312 [EGOI2021] Lanterns / 灯笼

题目大意

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

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

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

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

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

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

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

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

1 ≤ n , k ≤ 2 × 1 0 3 1\leq n,k\leq 2\times 10^3 1≤n,k≤2×103

时间限制 3000 m s 3000ms 3000ms，空间限制 1024 M B 1024MB 1024MB。

题解

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

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

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

那么，转移式为

f i , j ← min ⁡ r j ≤ r t { f i , t + w t } f i , j ← min ⁡ l t < l i { f t , j + w t } f i , j ← min ⁡ l t < l i , r j < r t { f t , t + w t } \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} fi,j​fi,j​fi,j​​←rj​≤rt​min​{fi,t​+wt​}←lt​<li​min​{ft,j​+wt​}←lt​<li​,rj​<rt​min​{ft,t​+wt​}​

其中， t t t需要满足 l i ≤ t ≤ r j l_i\leq t\leq r_j li​≤t≤rj​。

在枚举 i , j i,j i,j的时候，我们要按 l i l_i li​从小到大枚举 i i i，按 r j r_j rj​从大到小枚举 j j j。

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

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

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

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

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

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