[ABC400F] Happy Birthday! 3 题解

考虑正难则反。问题转化为：

一个环上有 个物品，颜色分别为 ，每次操作选择两个数 使得 ，将 中的每个物品的颜色都设为 。（下文将这种操作称为“漂白”。）一次操作的代价为 。求将整个环漂白的最小总代价。

先断环为链。设 表示将 漂白的最小代价，那么显然有 。

设 表示使 能够漂白的最小代价，那么显然有 。当 时，有 。

答案即为 。