题目要求把所有计算机两两配对，并用一条可能经过若干座信号塔的电缆连接每一对计算机，使所有电缆的得分总和最大。既要确定每对计算机连接时使用信号塔的最优方式，也要确定计算机的最优配对方式。首先将所有计算机与信号塔从左到右排序。

子任务 1

该子任务只有一座信号塔。对任意一对计算机，可以比较直接连接与经过信号塔连接哪一种更优。这取决于信号塔到这对计算机中较近一台的距离。

我们断言，按顺序把相邻计算机配对一定最优。考虑两对区间相交的计算机；最优解中不需要出现这种情况。

• 如果两对都不使用信号塔，交换配对方式显然可以缩短距离、提高得分。
• 如果两对都连接信号塔，得分只取决于各计算机到信号塔的距离之和，所以如何配对都没有影响。
• 最后一种情况是其中一对连接信号塔，另一对不连接。不连接的那一对一定离信号塔更远，否则它也会选择连接信号塔。此时交换配对同样会减小距离之和。

子任务 2

计算机数量很少，可以枚举所有配对方案。还可以预处理全部 $n^2$ 对计算机之间经过信号塔的最优连接。

枚举电缆经过的最左和最右信号塔即可。显然，使长度最短的最优电缆会从左侧计算机出发，先到达最左信号塔，再前往最右信号塔，最后返回右侧计算机，并在途中经过二者之间的所有信号塔。

子任务 3

需要更高效地计算经过若干信号塔的最优连接。观察连接计算机 $a$ 与 $b$ 的电缆：其得分由 $a$ 与 $b$ 之间的距离和信号塔贡献、从 $a$ 向左延伸的贡献，以及从 $b$ 向右延伸的贡献组成。

对每台计算机，在 $O(nm)$ 的时间内预处理其最优向左延伸值 $l_i$ 和最优向右延伸值 $r_i$。这样便能在 $O(1)$ 的时间内计算任意两台计算机之间的最优电缆得分。

接下来要用动态规划求最优配对，时间复杂度为 $O(n^2)$。从左到右建立配对，并记录还有多少台计算机没有配对。定义 $f(i,u)$ 为处理前 $i$ 台计算机、其中仍有 $u$ 台未配对时的最大得分；状态值已经计入截至第 $i$ 台计算机的所有未配对计算机的贡献。

第 $i$ 台计算机可以开始一对新的配对，也可以与此前某台未配对计算机组成一对；具体关闭哪一台未配对计算机并不重要。

如果第 $i$ 台计算机开始一个新配对，转移得分为

这是因为，在计算机 $i-1$ 与 $i$ 之间的间隔上，有 $u-1$ 台未配对计算机的电缆跨过该间隔，每台产生贡献 $c_i$；$c_i$ 由距离和两台计算机之间的信号塔数共同决定。

类似地，如果第 $i$ 台计算机关闭一个尚未完成的配对，转移得分为

因为在前 $i-1$ 台计算机中，原本应有 $u+1$ 台尚未配对的计算机。

译注：英文原文在第二个转移式中写作 $f(i+1,u+1)$，但这与状态定义及紧随其后的“前 $i-1$ 台计算机”矛盾；此处按状态含义订正为 $f(i-1,u+1)$。

子任务 4

可以更高效地预处理每台计算机向左的最优延伸值 $l_i$ 和向右的最优延伸值 $r_i$。计算机 $i$ 的向左延伸可能停在计算机 $i-1$ 与 $i$ 之间的某座信号塔；如果延伸越过了计算机 $i-1$，该情形的最优值已经由 $l_{i-1}$ 给出。

因此，可以把预处理时间从上一子任务的 $O(nm)$ 优化到 $O(n+m)$。

子任务 5

先把所有计算机都视为一对中的起点或左端点：从每台计算机进行最优的向左延伸，并把电缆一直画到最右边界。接下来，需要选择一些计算机作为配对的终点或右端点。

选择某台计算机 $i$ 作为右端点，会加入它的最优向右延伸贡献，同时减去此前把它视作起点时的贡献，以及它所关闭的、一直延伸到最右边界的电缆贡献。记这一变化为 $d_i$。注意，$d_i$ 与被关闭电缆实际从哪里开始无关。

问题转化为：从变化数组 $d_i$ 中选出 $n/2$ 个元素，使总和最大，并满足对每个长度为 $i$ 的前缀，最多选择 $i/2$ 个元素。

该问题有一个高效的贪心解法。处理前 $i$ 个元素时，维护其中被选中的 $\lfloor i/2\rfloor$ 个元素。读入下一个元素后，先把它加入已选集合；若集合大小超过新的容量，就删除已选元素中的最小值。处理结束时，留下的就是最优解。

用堆维护已选元素，即可在 $O(n\log n)$ 的时间内实现这一贪心算法。它的最优性证明较繁琐，或需要借助更高级的技巧，不过算法本身很容易实现，也可以通过向评测系统提交程序进行检验。

生成式人工智能辅助说明

本文由 OpenAI Codex 根据用户提供的 CEOI 2026 第二日官方英文题解翻译、排版并统一数学公式格式；算法思路、论证与复杂度均来自原文。两处原文中与上下文矛盾的明显公式笔误已在译文中订正，并分别附有译注。