自动搬运

查看原文

来自洛谷，原作者为

	Hell0_W0rld 硬币抛出之后，正逆的转换从未改变。|| 主页链接：https://www.luogu.me/paste/2r0elp1j

搬运于2025-08-24 23:07:16，当前版本为作者最后更新于2024-12-21 12:36:00，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P11432 [COCI 2024/2025 #2] Blistavost

非常好的一道反向关路灯+挖掘性质的区间 dp 题。

题目大意

$N$ 个任务，每个任务要求 $[l_i,r_i]$ 的水晶灯只能在 $\geq t_i$ 的时刻操作，且要被全部熄灭。你需要完成所有任务。你移动一单位的时间是 $1$。你初始在 $0$。

解题思路

Subtask 1

显然你不可能在一个没有任务的点折返，这样你还不如不折返往前走或者待在你来到这个点的地方。把关键点 $t_i$ 提取出来。

于是我们可以 $dp_{S,i}$ 表示你完成了 $S$ 状态下的任务，停留在 $t_i$ 的位置。

时间复杂度 $O(n^2\times 2^n)$。

正解

首先我们注意到你从中间开始关还不如你在左右两端等到 $t_i$ 时刻开始一个个关。所以如果两端 $l_i,r_i$ 的水晶灯都被关掉了，这个任务必然已经完成了。

其次我们可以从 Subtask 1 的代码中寻找最优决策——我们可以发现其中必然有一个最优解是每次仅有一个坐标区间内的所有关键点都没有关掉，其他关键点都关掉了。

感性理解一下：

如果不是这样的话，我们考虑一个点深入开着的水晶灯的坐标区间。

如果从两侧到达该点的路径上所有点都可以关掉，我们可以顺路关完，显然更优。

否则我们可以等外面的开始，然后一路操作进来，这个点在必须要走的连通区间两端点的路径上，可以被顺路操作，没必要特地跑进来关灯。

所以我们可以设计出 dp 状态：$f[l][r][0/1]$ 表示还剩下 $[x_l,x_r)$ 或 $(x_l,x_r]$ 的坐标区间内所有点都亮着，我正在 $l$ 或者 $r$ 的最短时间。

转移是平凡的。

代码

#include<bits/stdc++.h>
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#define ll long long
#define ull unsigned long long
#define rep(i,l,r) for(ll i=(l);i<=(r);++i)
#define Rep(i,l,r) for(ll i=(r);i>=(l);--i)
#define all(x) x.begin(),x.end()
#define Set(x,y) memset(x,y,sizeof(x))
#define Cpy(x,y) memcpy(x,y,sizeof(x))
#define cll const long long
using namespace std;
template<class T>
void death(T s){cout<<s<<endl;exit(0);}
cll N=10009;
ll f[N][2],tmp[N][2];
vector<pair<ll,ll>>vc; 
ll x[N],t[N];
int main(){
	ll n;cin>>n;
	while(n--){
		ll a,b,t;cin>>a>>b>>t;
		vc.emplace_back(a,t);
		vc.emplace_back(b,t);
	}
	sort(all(vc));
	for(auto _:vc)x[++n]=_.first,t[n]=_.second;
	f[1][0]=max(x[1],t[1]);
	f[1][1]=max(x[n],t[n]);
	ll ans=4e18;
	Rep(len,1,n-1){
		rep(i,1,n)tmp[i][0]=tmp[i][1]=4e18;
		rep(l,1,n-len+1){
			ll r=l+len-1;
			ll &g0=tmp[l][0],&g1=tmp[l][1];
			if(l>1){
				g0=min(g0,f[l-1][0]+x[l]-x[l-1]);
				g1=min(g1,f[l-1][0]+x[r]-x[l-1]);
			}
			if(r<n){
				g0=min(g0,f[l][1]+x[r+1]-x[l]);
				g1=min(g1,f[l][1]+x[r+1]-x[r]);
			}
			g0=max(g0,t[l]);
			g1=max(g1,t[r]);
			if(len==1)ans=min(ans,g0);
		}
		swap(f,tmp);
	}
	cout<<ans<<endl;
	return 0;
}