![【题解】[COCI 2024/2025 #2] 流明 / Blistavost](http://pic.xiahunao.cn/yaotu/【题解】[COCI 2024/2025 #2] 流明 / Blistavost)
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后面代码会讲详见代码注释#includebits/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; }
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后面代码会讲详见代码注释#includebits/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; }
