[ICPC 2022 Yokohama R] New Year Festival 题解

· · 题解

观察最终事件排列的形态，有结论：对于每个极长连续段（即极长的、相邻的若干个事件，满足它们之间没有任何间隔），必然存在至少一个事件，满足它的开始时间是它对应的分段函数图像上的一个顶点。证明也很简单，若一个极长连续段中没有任何一个事件在顶点上，可以平移整个连续段直到存在某个事件位于顶点上；若平移过程中碰到了别的连续段，那么它们可以合并成一个新的连续段，这个连续段就不是极长的了。

着重考虑那几个位于顶点的事件，称这些事件为关键事件。两个关键事件之间，存在的事件必然是一部分紧贴着左边的关键事件，一部分紧贴着右边的关键事件。尝试进行一个 DP，按照 x 坐标依次考虑每个顶点，每次转移可以新加入一个关键事件，考虑它和前一个关键事件之间的其他事件：记 \operatorname{len}(S) 表示事件集合 S 内所有事件持续时间之和，设两个关键事件之间的时间间隔为 g（注意并不是顶点坐标差，而是前一个事件结束，到后一个事件开始，中间那段时间的长度），紧贴左边事件集合为 S_l，紧贴右边事件集合为 S_r，那么 S_l 和 S_r 合法当且仅当 S_l\cap S_r=\varnothing 并且 \operatorname{len}(S_l)+\operatorname{len}(S_r)\le g。

对于每个顶点 i，预处理 l_{i,S} 表示当 i 对应的事件位于该顶点时，紧贴着它在左边放入集合 S 中的事件时，这些事件产生的最小代价和是多少，右边（r_{i,S}）同理。这个可以用一个简单的状压 DP 来实现，每次在末尾加入一个事件并计算新增的代价即可。

设转移对应的顶点为 j,i（j 在 i 之前），先提前计算出一个信息 g_S，表示 j,i 对应的两个关键事件之间出现的其他事件集合为 S 时，代价和最小是多少：使用枚举子集的技巧枚举两个不交集合 S_l,S_r，若满足前文所述的条件，那么 g_{S_l\cup S_r}\gets\min\{g_{S_l\cup S_r},r_{j,S_l}+l_{i,S_r}\}。

设 f_{i,S} 表示最后一个关键点位于第 i 个顶点、目前出现的事件集合为 S 时的答案，对于 S\cap T=\varnothing 有转移 f_{i,S\cup T\cup\{e_i\}}\gets\min\{f_{i,S\cup T\cup\{e_i\}},f_{j,S}+g_T\}，其中 e_i 为顶点 i 对应的事件编号，同样使用枚举子集的方法计算。

记得最后一个关键事件之后还可能有一些和它贴着的事件，简单处理一下即可。

时间复杂度 O(m^23^n)，瓶颈在于枚举两个转移点之后进行的子集 (\min,+) 卷积。如果实现的时候注意一点，常数会非常小，在 7\mathrm{s} 的时限下可以轻松通过。另外这题细节也不少，写代码的时候一定要细心。

截至本题解发布时，本人的解法在单个测试点上的最大用时为 59\mathrm{ms}（洛谷评测机），是洛谷和 QOJ 上的最优解，且速度为次优解 7 倍左右。考虑到代码较为冗长，故不在此放出。若对此有需求可以在评论区留言。