ColorfulChocolates

作者：罗哲正 钟知闲

关键词：枚举

题目简述

一列$n$个巧克力，第$i$个巧克力的颜色为$chocolate[i]$。

你可以进行不超过$maxSwaps$次操作，每次操作为交换相邻两个巧克力的位置。

最大化这一列巧克力的伸展度，伸展度的定义为最长连续同色巧克力区间内的巧克力数目。

$1 \leq n \leq 50;'A' \leq chocolate[i] \leq 'Z';1 \leq maxSwaps \leq 2500.$

算法

注意到$n$的数据范围只有$50$，我们不妨枚举一种颜色$c$，并用颜色为$c$的巧克力来构成连续同色区间。
由于交换相同颜色的巧克力是没有意义的，同色巧克力之间的相对顺序不会改变。于是如果我们把所有颜色为$c​$的巧克力拿出来排成一列，一定是其中某个子段段组成了最后的连续同色巧克力区间。
我们接着枚举这个子段并考虑能否使用不超过$maxSwaps$次操作把他们聚集到一起。

先考虑一个显然的结论：这个子段中至少有一个巧克力没有改变位置。

考虑若所有的巧克力都改变了位置，那么我们把最后的连续同色巧克力区间往左或右移动$1$个位置，至少有一种移动会使得交换次数不增大，而移动后的区间一定和初始区间有交集。实际上，中位数位置的巧克力不改变其位置是最优解。
那么我们从小到大枚举不改变位置的巧克力，并维护需要的交换次数$\sum |init\_pos_i - final\_pos_i|$即可。

颜色枚举量为$alphabet=26$，区间枚举量为$O(n^2)$，不变巧克力枚举量为$O(n)$。
于是时间复杂度就是$O(alphabet\cdot n^3)$。

优化

这题的枚举可以进一步优化。

假如已经枚举了一种颜色 $c$ 和一段区间，枚举的区间中颜色为 $c$ 的巧克力位置为 $i_0 < i_1 < ... < i\_{k-1}$。上文提到，令位于 $i\_{\lfloor\frac{k}{2}\rfloor}$ 的巧克力不动是最优的。以下补充证明：

假如存在最优解，位于 $i\_{\lfloor\frac{k}{2}\rfloor}$ 的巧克力被左移了 $x$ 的距离，那么将解区间右移 $x$ 的距离，由于对任意整数 $\lfloor\frac{k}{2}\rfloor\le j < k$，有 $i_j \ge i\_{\lfloor\frac{k}{2}\rfloor}+j-\lfloor\frac{k}{2}\rfloor$，即位于 $i\_{\lfloor\frac{k}{2}\rfloor}$ 及其右侧的巧克力都不在目标位置左侧，所以它们到目标位置的距离都减少了 $x$，同时其左边的巧克力到目标位置的距离最多增加 $x$，因为 $k-\lfloor\frac{k}{2}\rfloor\ge\lfloor\frac{k}{2}$，故总距离不会变大。

同理可以证明如果最优解被右移了 $x$，左移 $x$ 同样不会使总距离变大。因此存在最优解位于 $i\_{\lfloor\frac{k}{2}\rfloor}$ 的巧克力不动。

因此，枚举算法可以这样优化：枚举颜色 $c$，取出该颜色的所有位置后枚举区间左端点 $l$，从小到大枚举右端点 $r$，枚举时维护区间中位数位置，以及最少的交换次数（考虑中位数右边的位置和与中位数左边的位置和之差，可以快速更新交换次数）。这样的复杂度为 $O(n^2)$，当只有一种颜色时取到最坏复杂度。

还可以继续优化。注意到枚举区间时，$r$ 每增加时最少交换次数不会减小，$l$ 每增加时最少交换次数不会增大，因此可以用 two pointers 技巧，枚举 $l$ 时在上次枚举的基础上增加 $r$ 直到交换次数超过 $\mathrm{maxSwap}$。这样总复杂度降到了每种颜色出现次数之和级别，即 $O(n)$。

当然，由于本题数据规模很小，这样的优化没有什么必要，反而增加了代码难度（不过如果数据规模增加，优化便派上用场了）。有一种实现方式可以减少一些细节：对每种颜色，将第 $j$ 个该颜色的位置标号减去 $j$，这样就相当于把所有点移到同一个点的最小交换次数，也就更容易维护了。

总结

要善于使用枚举法来发挥计算机的长处，很多时候数学推导出得出的结论不如一两个for循环来的精妙。