← 返回题目列表

AtCoder · joi2019ho_c

C. 种菜很有趣 3

中文机器翻译题面 查看原题

配点: 100 点

JOI 正在利用他多年的家庭园艺经验在他的花园里种植一种名为 Joy Grass 的新植物。园内东西向排列 从西侧开始有 N 花盆。 它们的编号最大为 1 到 N 。欢乐草就是一切 N 每个花盆中都有库存 1 一一种下。

当JOI春天去查看情况时,他发现欢乐草的叶子颜色鲜艳,与他的预期相反。此外,我注意到欢乐草的生长速度没有我预期的那么快。 JOI 你对这些事情感到好奇,所以你在书上查了一下,发现了以下内容:

  • 乔伊·库萨 3 有不同的类型,每种都有红色、绿色和黄色的叶子。
  • 如果你在附近放置叶子颜色相同的欢乐草,它的生长将会受到抑制。

因此,JOI决定重新排列喜悦草,让相同叶色的喜悦草不会相邻。这时JOI君就在旁边 2 你只能更换两颗喜悦草。换句话说,1 JOI 你是一个只进行一次操作的种植者 i (1 \leqq i \leqq N - 1) 可选 1 选择一个,花盆 i 欢乐草和花盆 您可以替换 i + 1 中的欢乐草。 JOI 你想用尽可能少的操作来避免两片叶子颜色相同的欢乐草彼此相邻。

给定欢乐草的数量和每个欢乐草叶子的颜色,编写一个程序,找出重新排列具有相同叶子颜色的欢乐草以使它们彼此不相邻所需的最少操作数。


入力

输入是按以下格式从标准输入给出的。

N
S

S 是长度 字符串 N 。 i 文字目 (1 \leqq i \leqq N) 是一个花盆 如果 i 中种植的喜悦草的叶子颜色是红色 R,如果绿色 G,如果是黄色 Y 。

出力

显示标准输出所需的最少操作数。 输出为 1 行。然而,如果无法重新排列具有相同叶子颜色的欢乐草,使它们不彼此相邻,则改为 输出 -1 。 它是一个


制約

  • 1 \leqq N \leqq 400.
  • S 是长度 字符串 N 字符串。
  • S 中的每个字符是 R,G,Y 。

小課題

  1. (5 点) N \leqq 15.
  2. (55 点) N \leqq 60.
  3. (15 点) S 中的每个字符是 R,G 。
  4. (25 点)没有额外的限制。

入力例 1

5
RRGYY

出力例 1

2

在此输入示例中,您可以通过执行以下操作来防止具有相同叶子颜色的欢乐草彼此相邻。

  • 一、播种机 替换 3 欢乐草和花盆 您可以替换 4 中的欢乐草。
  • 接下来是花盆 2 欢乐草和花盆 您可以替换 3 中的欢乐草。

如果你这样做,那排欢乐草将会 它看起来像 RYRGY 。1 通过执行以下操作,无法防止具有相同叶子颜色的欢乐草彼此相邻。2 。


入力例 2

6
RRRRRG

出力例 2

-1

在这个输入示例中,无论您如何操作,都无法阻止具有相同叶子颜色的欢乐草彼此相邻。


入力例 3

20
YYGYYYGGGGRGYYGRGRYG

出力例 3

8