题解

思路

关键是确定第一次把信留给 R 的位置，并证明从该位置起每个新人物段的首封信都可以选择 R。这样，各段首封信的等待长度会望远镜求和，而同段其余信件可以独立决策。

做法

子任务 1：枚举寄送方案

当 $n\le18$ 时，用一个二进制集合表示哪些事件选择把信留给 R。没有选择的事件费用为 $d$；选择的事件向后寻找第一个“人物相反且也选择 R”的事件，其时刻就是取信时刻，若不存在则取信时刻为 $t_{n+1}$。枚举全部集合即可。

复杂度为 $O(n^2 2^n)$。

子任务 2：枚举第一封留给 R 的信

若没有信留给 R，总费用为 $nd$。否则枚举第一封留给 R 的信为第 $i$ 封，前 $i-1$ 封都直接寄送。

从 $i$ 开始，把相同人物的连续事件看成一个段。当前已经有人把信留给 R 后，下一个人物段的第一封信选择 R 一定不劣：提前到达会让至少一封等待中的来信更早被取走，而自己新写的信虽然会多存放同样长的时间，但增加的费用至多抵消减少的费用。因此，从第 $i$ 个事件开始，每个连续段的首封信都可以固定选择 R。

一个段的首封信会在下一段首个事件（最后一段则在喝茶时刻）被取走。段内其余信不影响到访时刻，分别选择直接寄送与留给 R 中费用更小的一种。枚举 $i$ 后逐段计算，复杂度为 $O(n^2)$。

子任务 3：线性扫描

固定第一封留给 R 的信为第 $i$ 封。各段首封信的保管时间之和发生望远镜消去，恰好为 $t_{n+1}-t_i$，费用是

同一人物连续段中，除首封以外的一封信若发生在时刻 $t_j$，它选择 R 时会在下一人物段的首个时刻 $T$ 被取走，因此贡献

从后向前扫描。维护右侧下一人物段的首个时刻 next_time，以及当前后缀所有“段内非首封”信件的最优贡献之和 extra。于是以 $i$ 为第一封留给 R 的信时，总费用为

再与全部直接寄送的 $nd$ 取最小值即可。

费用最大可能达到 $10^{13}$，必须使用 64 位整数。

复杂度

三个子任务算法的时间复杂度依次为 $O(n^2 2^n)$、$O(n^2)$、$O(n)$；空间复杂度均为 $O(n)$。

正确性说明

任取一个至少使用一次 R 的最优方案，并令第 $i$ 封信为第一次使用 R。此前只能直接寄送。第 $i$ 封信之后，若某人物段需要到 R 取走等待中的来信，把该段第一次到访移动到段首不会增大总费用，因此可规范化为每段首封必选 R。各段首封产生的等待区间首尾相接，总长度为 $t_{n+1}-t_i$；同段其余信件不会改变任何到访时刻，可以独立选择两种方式的较小费用。算法枚举了 $i$ 的全部可能并准确计算相应规范化方案，另行考虑全部直送方案，所以得到全局最优值。