P11432 [COCI 2024/2025 #2] 流明 / Blistavost - 洛谷 (luogu.com.cn)
这题名字很好听哦。璀璨流明 / 流明水晶像是小马宝莉里哪匹小马的名字。
注意到数据范围，时间复杂度不可能带 log，初步判断是做法。
考虑最优情况：
第一，能回头吗？
当然是能的，在保证 [A 区间] < [B 区间] 的限制，当且仅当：
如果 t_A > t_B + (R_B - R_A)，就回头！（这只是举个能回头的例子，实际情况要复杂得多，无法保证两个区间不相交）
第二，在已走过区间里的未熄灭区间，一定是连续的吗？
答案是不一定，但我们可以强行让它连续。
如果已走过区间 亮——暗——亮，中间那块暗的，还不如等到最后一次走过这块区域的时候灭。
这样会变得好处理很多。
第三，所有回头操作一定要在处理区间端点执行吗？
当然啦，毫无疑问的。
不然你多走一段是何意味(#`O′)
现在我们可以只关注区间端点，将它们离散化。
设计区间 dp 状态为：
dp[l][r][0]：守卫在 l，只剩 [l, r] 没有被熄灭 的最小时间 dp[l][r][1]：守卫在 r，只剩 [l, r] 没有被熄灭 的最小时间 // 为什么是闭区间？因为守卫可以选择不熄灭那个位置上的灯，这样方便计算 // 隐含规则：必须在合法的时间才能走到 l 或者 r（后面代码会讲）详见代码注释：
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 5010; struct node { LL x, t; } a[N * 2]; LL dp[2 * N][2], p[2 * N][2]; // 两倍 N 就会炸空间，使用滚动数组 // dp[l][r][0]：守卫在 l，只剩 [l, r] 没有被熄灭 的最小时间 // dp[l][r][1]：守卫在 r，只剩 [l, r] 没有被熄灭 的最小时间 // 为什么是闭区间？因为守卫可以选择不熄灭那个位置上的灯，这样方便计算 // 隐含规则：必须在合法的时间才能走到 l 或者 r（后面代码会讲） bool cmp(node na, node nb) { if (na.x != nb.x) { return na.x < nb.x; // 保证 dp 处理从左到右 } return na.t < nb.t; // 按时间顺序排（一般情况不影响答案） } int main () { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; for (int i = 1; i <= n; i ++) { LL l, r, t; cin >> l >> r >> t; a[i * 2 - 1] = {l, t}; a[i * 2] = {r, t}; } n *= 2; sort (a + 1, a + n + 1, cmp); memset(dp, 0x7f, sizeof(dp)); LL inf = dp[0][0]; memset(p, 0, sizeof(p)); // p 数组代表的是上一个 len 的 dp 数组 // 第一次转移时范围是 [1, n]，不存在什么 len = n + 1 // 所以不会用到，不初始化也行 dp[1][0] = max(a[1].x, a[1].t); // dp[1][n][0] dp[1][1] = max(a[n].x, a[n].t); // dp[1][n][1] LL ans = inf; for (int len = n; len >= 1; len --) { for (int i = 1; i + len - 1 <= n; i ++) { int j = i + len - 1; // 下面二维数组，想象中间维数插了个 [j] if (i >= 2) { // 守卫从 i - 1 走到 i dp[i][0] = min(dp[i][0], p[i - 1][0] + a[i].x - a[i - 1].x); // 守卫从 i - 1 走到 j dp[i][1] = min(dp[i][1], p[i - 1][0] + a[j].x - a[i - 1].x); } if (j <= n - 1) { // 守卫从 j + 1 走到 i dp[i][0] = min(dp[i][0], p[i][1] + a[j + 1].x - a[i].x); // 守卫从 j + 1 走到 j dp[i][1] = min(dp[i][1], p[i][1] + a[j + 1].x - a[j].x); } dp[i][0] = max(dp[i][0], a[i].t); dp[i][1] = max(dp[i][1], a[j].t); // 这里就是隐含规则，当前状态 i 或 j 是没有熄灭的 // 但你必须在 a[i].t 或 a[j].t 及之后时刻到这里 if (len == 1) { // 当 len = 1 时，代表 i = j，只有 [i, i] 没被熄灭 // 手动操作一下就熄灭了，直接统计答案 ans = min(ans, min(dp[i][0], dp[i][1])); } } for (int i = 1; i <= n; i ++) { p[i][0] = dp[i][0]; p[i][1] = dp[i][1]; dp[i][0] = inf; dp[i][1] = inf; // 更新 p 数组，并初始化 dp数组 } } cout << ans << "\n"; return 0; }
