题目理解

我们有 $N$ 个花盆排成一排，每个花盆中的 Joy 草颜色为 R、G、Y 中的一种。每次操作可以交换相邻的两个花盆。

目标：通过最少的相邻交换次数，使得最终的排列中没有两个相邻花盆颜色相同。

关键观察

1. 可行性分析

首先需要判断是否有解。设三种颜色的数量分别为 $cnt_R$, $cnt_G$, $cnt_Y$。

必要条件：最多的颜色数量不能超过 $\lceil \frac{N}{2} \rceil$

因为如果某种颜色太多，根据鸽巢原理，必然会出现相邻同色。

更精确地，如果 $\max(cnt_R, cnt_G, cnt_Y) > \lfloor \frac{N+1}{2} \rfloor$，则无解，输出 $-1$。

2. 问题转化

我们需要找到一个目标排列，满足：

• 相邻颜色不同
• 从初始排列通过相邻交换得到该排列的代价最小

关键洞察：相邻交换的次数等于初始排列到目标排列的逆序数。

因此问题转化为：在所有满足相邻颜色不同的排列中，找到与初始排列逆序数最小的那个。

算法思路

1. 动态规划状态设计

由于 $N \leq 400$，直接枚举所有排列不可行。我们需要设计高效的 DP。

设 $dp[i][r][g][last]$ 表示：

• 考虑了前 $i$ 个位置
• 已经放置了 $r$ 个 R，$g$ 个 G
• 最后一个位置的颜色是 $last$（0:R, 1:G, 2:Y）

时的最小逆序数。

状态大小：$O(N^3)$，对于 $N=400$ 来说太大（$400^3 = 64,000,000$）。

2. 状态优化

注意到 $r + g + y = i$，其中 $y$ 是 Y 的数量，所以我们可以去掉一维：

$dp[i][r][last]$ 表示：

• 考虑了前 $i$ 个位置
• 已经放置了 $r$ 个 R
• 最后一个位置的颜色是 $last$

此时 $g = i - r - y$ 可以推算出来。

状态大小：$O(N^2)$，对于 $N=400$ 是 $160,000$，可以接受。

3. 状态转移

对于状态 $dp[i][r][last]$，我们考虑在第 $i+1$ 个位置放什么颜色：

• 如果放 R：需要 $last \neq 0$，且 $r < cnt_R$
• 如果放 G：需要 $last \neq 1$，且 $g < cnt_G$
• 如果放 Y：需要 $last \neq 2$，且 $y < cnt_Y$

逆序数计算：当我们决定在第 $i+1$ 个位置放某种颜色时，需要计算这个颜色在初始序列中所有尚未使用的该颜色元素中，有多少个原本在更前面的位置（这会产生逆序）。

4. 逆序数预处理

为了快速计算逆序数，我们可以预处理：

• $pos[c][k]$：第 $k$ 个颜色 $c$ 在初始序列中的位置
• 在 DP 过程中，记录每种颜色已经使用了多少个

当我们决定使用第 $m$ 个颜色 $c$ 的元素时，逆序数的增加量为：

• 初始位置在 $pos[c][m]$ 之前且尚未使用的其他颜色元素数量

这可以通过维护每种颜色的使用指针来快速计算。

算法步骤

1. 可行性检查：

   • 计算 $cnt_R, cnt_G, cnt_Y$
   • 如果 $\max(cnt_R, cnt_G, cnt_Y) > \lfloor \frac{N+1}{2} \rfloor$，输出 $-1$

2. 预处理：

   • 记录每种颜色在初始序列中的位置
   • 初始化 DP 数组为无穷大

3. 动态规划：

   • 初始状态：$dp[0][0][0] = dp[0][0][1] = dp[0][0][2] = 0$
   • 对于每个 $i$ 从 $0$ 到 $N-1$：
     • 对于每个 $r$ 从 $\max(0, i-cnt_G-cnt_Y)$ 到 $\min(i, cnt_R)$：
       • 对于每个 $last$ 从 $0$ 到 $2$：
         • 如果状态可达，尝试放置三种颜色

4. 计算逆序数增量：

   • 对于要放置的颜色 $c$，选择该颜色中尚未使用的最前面一个
   • 计算这个选择产生的逆序数

5. 答案提取：

   • $\min(dp[N][cnt_R][0], dp[N][cnt_R][1], dp[N][cnt_R][2])$

复杂度分析

• 状态数：$O(N^2)$
• 状态转移：每个状态尝试 $3$ 种选择
• 逆序数计算：通过预处理可以 $O(1)$ 计算
• 总复杂度：$O(N^2)$，对于 $N=400$ 可以接受

特殊情况

Subtask 3：只有 R 和 G 两种颜色

这种情况更简单：

• 可行性条件：$|cnt_R - cnt_G| \leq 1$
• 状态可以进一步简化
• 实际上就是两种颜色的交替排列

总结

这道题的核心在于将相邻交换问题转化为逆序数最小化问题，并通过动态规划在满足颜色约束的条件下寻找最优解：

1. 问题转化：相邻交换次数 = 逆序数
2. 可行性分析：基于颜色数量的必要条件
3. 状态设计：使用 DP 记录已放置的颜色数量和最后颜色
4. 逆序数计算：通过预处理和指针维护快速计算
5. 复杂度优化：通过状态维度的合理设计控制复杂度

这种"逆序数最小化 + 约束满足"的思路在排列优化问题中非常常见，是算法竞赛中的重要技巧。