#P18954. [Mladen Manev 2022 AT4] snowcleaning / 动态充电站与清雪
[Mladen Manev 2022 AT4] snowcleaning / 动态充电站与清雪
动态充电站与清雪
一条道路是线段 。清雪车每次充满电后可以清理总长为 的积雪。沿道路有 个充电站,位置严格递增;充电瞬间完成,可以随时充满。
清雪车可以带电或不带电行驶,行驶一单位距离需要一单位时间。只有清理积雪才消耗电量;经过某段道路时可以选择清理,也可以不清理。可以重复经过已经清理的路段;转向没有额外开销。
连续处理 天。每天开始时整条道路重新被积雪覆盖,电池为空,车位于当日给出的 。当夜有一些坏站修复、一些正常站损坏;站点状态持续到后续日期,且每天至少有一个站正常。初始全部站正常。
求每天清理整条道路所需的最短时间。车最后可以停在任意位置,不必返回充电站。
输入格式
第一行 。第二行严格递增的 个站点位置 。
接下来每一天有三行:第一行 ,表示修复站数、损坏站数及车的起始位置;第二行为递增的 个修复站编号,第三行为递增的 个损坏站编号。编号从 开始,空列表对应空行。
修复的站此前一定损坏,损坏的站此前一定正常;当日两类编号互不相交。
输出格式
行,每行一个 64 位整数,表示该天的最短清雪时间。
数据范围
,,,。全部日期修复数之和不超过 ,损坏数之和也不超过 ,二者分别限制。
样例
3 5 2 1
2 3 5
0 1 3
2
9
从位置 3 先到正常站 2 充电,清理左侧后返回;再充电清理右侧,并利用站 5,最终可以停在位置 4,总行驶距离为 9。
本题为波兰 XXVIII OI 决赛第一天 Surowa zima(2021),由本网站 2022 年训练赛选用。官方解法见 OI 分析。
来源与数据说明
2022 年 Dr. Mladen Manev,AT4,原题名 snowcleaning。赛事资料,原文题面见附件 statement.pdf。
原官方测试数据未能获取,本题使用依据原题规格编写的自建测试数据,并非官方原始数据。总分为 100 分。