专栏文章

题解：P9312 [EGOI 2021] Lanterns / 灯笼

UUKE_Automation
P9312题解参与者 8已保存评论 7

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
7 条
当前快照
1 份
快照标识符
@mipp40dp
此快照首次捕获于
2025/12/03 15:38
3 个月前
此快照最后确认于
2025/12/03 15:38
3 个月前
查看原文

P9312 [EGOI 2021] Lanterns / 灯笼

Link\text{Link}
先考虑朴素的 dp 怎么做：枚举起点 ii，然后令 dp(l,r)dp(l,r) 表示此时合法海拔范围在 [l,r][l,r] 的最小花费。由于起点确定，海拔范围 [l,r][l,r] 表示的区间就确定了。转移的时候枚举区间中的灯笼，能转移当且仅当这个灯笼的 [Ai,Bi][A_i,B_i] 与 [l,r][l,r] 有交集。复杂度是 O(n3k)O(n^3 k) 的。
考虑优化，首先要优化的就是将枚举起点这一步搞掉，方法很简单，转置一手即可。然后由于起点未知，[l,r][l,r] 能表示的区间也就不知道了，所以还要记录区间中的一个点来转移。于是设 dp(l,r,i)dp(l,r,i) 表示当前走到 ii，合法范围在 [l,r][l,r]，从这个状态开始走完还需要的最小花费。
这样做其实没有优化复杂度，不过这时候的瓶颈就在状态上了。考虑怎样优化状态，我们想办法把海拔上下界和区间位置这两个信息压缩起来，这时候不难想到，由于上下界是由区间中某两个点确定的，所以只需要知道这两个点的位置，就可以计算出区间位置和上下界了。所以设 dp(u,v)dp(u,v) 表示当前海拔下界为 AuA_u，海拔上界为 BvB_v，区间经过 u,vu,v 还需要的最小花费。
考虑转移，枚举区间中的灯笼，然后依然判断交集并转移即可，分类讨论一下有：
  • f(u,v)=min⁡(f(u,v′)+Wv′)f(u,v)=\min(f(u,v')+W_{v'})，要求 Bv<Bv′B_v<B_{v'}；
  • f(u,v)=min⁡(f(u′,v)+Wu′)f(u,v)=\min(f(u',v)+W_{u'})，要求 Au>Au′A_u>A_{u'}；
  • f(u,v)=min⁡(f(p,p)+Wp)f(u,v)=\min(f(p,p)+W_{p})，要求 Bv<BpB_v<B_{p} 且 Au>ApA_u>A_p；
此时的复杂度是 O(k2n)O(k^2 n) 的，瓶颈在转移。考虑如何优化，先看第一种转移。由于整个过程实际上还是类似区间 dp，所以我们在枚举的时候 uu 应该按 AA 从小到大枚举，vv 应该按 BB 从大到小枚举。这时候会发现，对于 Bj>BiB_j>B_i，如果 f(u,v′)f(u,v') 无法转移到 f(u,j)f(u,j)，那么它同样不可能转移到 f(u,i)f(u,i)，原因显然。
于是我们就可以对 uu 维护一个小根堆，存储所有还可以转移的 f(u,v′)+Wv′f(u,v')+W_{v'} 的值。当我们枚举到一个 f(u,v)f(u,v) 的时候，先弹出堆顶已经不能转移的 v′v'，然后此时的堆顶就是一个合法转移点，直接转移即可。这样的话对于同一个 uu，每个 vv 最多进堆一次，出堆一次，复杂度是 O(klog⁡k)O(k\log k) 的，所以总复杂度就是 O(k2log⁡k)O(k^2\log k)。
对于第二种转移优化方式和第一种类似，不再赘述。现在看第三种转移，一个经典的思路是我们分步转移，也就是 f(p,p)→f(p,v)/f(u,p)→f(u,v)f(p,p)\to f(p,v)/ f(u,p) \to f(u,v) 这样转移。这时会发现 f(p,v)f(p,v) 或者 f(u,p)f(u,p) 都是不合法的状态，不过问题不大，我们特判一下，把它们的值赋为 f(p,p)f(p,p) 即可。
如此我们的 dp 就优化到了 O(k2log⁡k)O(k^2 \log k)，可以通过。
CPP
#include <bits/stdc++.h>
#define il inline

using namespace std;

const int Maxn = 2e3 + 5;
const int Inf = 2e9 + 5;
const int Mod = 1e9 + 7;
il int Add(int x, int y) {return x + y >= Mod ? x + y - Mod: x + y;} il void pls(int &x, int y) {x = Add(x, y);}
il int Del(int x, int y) {return x - y < 0 ? x - y + Mod : x - y;} il void sub(int &x, int y) {x = Del(x, y);}
il int max(int x, int y) {return x >= y ? x : y;} il void chkmax(int &x, int y) {x = (x >= y ? x : y);}
il int min(int x, int y) {return x <= y ? x : y;} il void chkmin(int &x, int y) {x = (x <= y ? x : y);}
il int qpow(int a, int b) {int res = 1; for(; b; a = 1ll * a * a % Mod, b >>= 1) if(b & 1) res = 1ll * res * a % Mod; return res;}
il int Inv(int a) {return qpow(a, Mod - 2);}
template <typename T>
il void read(T &x) {
	x = 0; char ch = getchar(); bool flg = 0;
	for(; ch < '0' || ch > '9'; ch = getchar()) flg = (ch == '-');
	for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
	flg ? x = -x : 0;
}
template <typename T>
il void write(T x, bool typ = 1) {
	static short Stk[50], Top = 0;
	x < 0 ? putchar('-'), x = -x : 0;
	do Stk[++Top] = x % 10, x /= 10; while(x);
	while(Top) putchar(Stk[Top--] | 48);
	typ ? putchar('\n') : putchar(' ');
}
il void IOS() {ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);}
il void File() {freopen("lantern.in", "r", stdin); freopen("lantern.out", "w", stdout);}
bool Beg;

int n, m, h[Maxn];
int p[Maxn], c[Maxn], a[Maxn], b[Maxn];
int id1[Maxn], id2[Maxn];
int l[Maxn][2], r[Maxn][2];
int dp[Maxn][Maxn];
#define pii pair<int, int>
#define mk make_pair
priority_queue <pii, vector<pii>, greater<pii>> q1[Maxn], q2[Maxn]; 

bool End;
il void Usd() {cerr << (&Beg - &End) / 1024.0 / 1024.0 << "MB " << (double)clock() * 1000.0 / CLOCKS_PER_SEC << "ms\n"; }
int main() {
	File();
	read(n), read(m);
	for(int i = 1; i <= n; i++) read(h[i]);
	for(int i = 1; i <= m; i++) read(p[i]), read(c[i]), read(a[i]), read(b[i]), id1[i] = id2[i] = i;
	sort(id1 + 1, id1 + m + 1, [](int x, int y){return a[x] < a[y];});
	sort(id2 + 1, id2 + m + 1, [](int x, int y){return b[x] > b[y];});
	for(int i = 1; i <= m; i++) {
		l[i][0] = l[i][1] = r[i][0] = r[i][1] = p[i];
		while(l[i][0] > 1 && h[l[i][0] - 1] >= a[i]) l[i][0]--;
		while(r[i][0] < n && h[r[i][0] + 1] >= a[i]) r[i][0]++;
		while(l[i][1] > 1 && h[l[i][1] - 1] <= b[i]) l[i][1]--;
		while(r[i][1] < n && h[r[i][1] + 1] <= b[i]) r[i][1]++;
	}
	for(int i = 1; i <= m; i++) { //最小值 
		for(int j = 1; j <= m; j++) { //最大值 
			int x = id1[i], y = id2[j];
			dp[x][y] = Inf;
			if(p[x] < l[y][1] || p[x] > r[y][1] || p[y] < l[x][0] || p[y] > r[x][0]) continue;
			if(a[y] < a[x] && b[x] > b[y]) continue;
			int pl = max(l[x][0], l[y][1]), pr = min(r[x][0], r[y][1]);
			if(pl == 1 && pr == n) dp[x][y] = 0;
			else if(a[y] < a[x]) dp[x][y] = dp[y][y];
			else if(b[x] > b[y]) dp[x][y] = dp[x][x];
			else {
				while(!q1[x].empty()) {
					int t = q1[x].top().second;
					if(p[t] < pl || p[t] > pr || b[t] < a[x] || a[t] > b[y]) q1[x].pop();
					else break;
				}
				if(q1[x].size()) chkmin(dp[x][y], q1[x].top().first);
				while(!q2[y].empty()) {
					int t = q2[y].top().second;
					if(p[t] < pl || p[t] > pr || b[t] < a[x] || a[t] > b[y]) q2[y].pop();
					else break;
				}
				if(q2[y].size()) chkmin(dp[x][y], q2[y].top().first);
			}
			if(dp[x][y] != Inf) {
				q1[x].push(mk(dp[x][y] + c[y], y));
				q2[y].push(mk(dp[x][y] + c[x], x));
			}
		}
	}
	for(int i = 1; i <= m; i++) {
		if(h[p[i]] < a[i] || h[p[i]] > b[i] || dp[i][i] == Inf) write(-1);
		else write(dp[i][i] + c[i]);
	}
	Usd();
	return 0;
}

评论

共 7 条评论，欢迎与作者交流。

正在加载评论...