题解：P11432 [COCI 2024/2025 #2] 流明 / Blistavost
Hell0_W0rld
·
·
题解
P11432 [COCI 2024/2025 #2] Blistavost
非常好的一道反向关路灯+挖掘性质的区间 dp 题。
题目大意
### 解题思路
#### 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$ 的最短时间。
转移是平凡的。
### 代码
```cpp
#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;
}
```