IOI2017 - Wiring

给定数轴上位置两两不同的 \(n\) 个红点，\(m\) 个蓝点，你现在需要接若干线，使得每个点都至少和一个异色点直接连接，最小化接线总长度。\(n,m\leqslant 100000\)，\(r_i,b_i\leqslant 10^9\)。

\(r,b\) 分别是红蓝点的位置，输入已经排好序。
考虑 \(r_n<b_1\) 的情况，假设 \(n\leqslant m\)，可以发现一种最优方案是每个红点都接不同的蓝点，剩下多余的蓝点再全去接红点，通过分析贡献可以知道这样达到了答案的最小值 \(\sum (r_n-r_i)+\sum (b_i-b_1)+\max(n,m)(b_1-r_n)\)。

现在考虑一般的情况，我们先说明以下结论：

• 对于任意四个点 rrbb/bbrr 且匹配是 1-3, 2-4 的情况的，我们可以改成 1-4, 2-3 的匹配方式，代价不变。
• 对于任意四个点 rbrb/brbr，不会出现 1-4, 2-3 匹配的情况，因为改成 1-2, 3-4 的匹配方式，代价更小。

根据这两个结论，可以得出我们最后的接线方案可以是把原序列划分成若干段，每一段都是先红后蓝或先蓝后红的形式，段内按照上面 \(r_n<b_1\) 的情况匹配，特殊地，对于段内颜色全部相同的，向旁边段的最近的颜色不同的点匹配。

考虑 dp，先把红蓝点归并，设新的点的坐标数组是 \(c\)，设 \(f_i\) 表示在 \(i\) 到 \(i+1\) 之间是分割线的最小代价，则答案是 \(f_{n+m}\)。

转移去枚举上一个断点，假设当前极长的同色段是 \([L,R]\)，上一段是 \([l,L-1]\)，那么有转移：

考虑去优化这个转移，注意到某一段只可能由前一段的状态转移而来，我们去拆开 \(\max\)，当进入一个新段时，处理出上一段每个点作为转移点，且 \(\max\) 分别被谁取到时的 dp 值，然后只需要取前后缀 \(\min\) 即可。复杂度 \(O(n)\)。

IOI2017 - Wiring

原文：https://www.cnblogs.com/AzusaCat/p/14690278.html