#P6360. 「JOI 2019 Final」有趣的家庭菜园 3

    ID: 5849 传统题 500ms 1024MiB 尝试: 4 已通过: 3 难度: 7 上传者: 标签>CF2200提高同字符有序匹配求最少相邻交换次数线性 DP一维前缀和状态维度消除滚动数组

「JOI 2019 Final」有趣的家庭菜园 3

题目描述

译自 JOI 2019 Final T3「たのしいたのしいたのしい家庭菜園 / Growing Vegetable is Fun 3」

家庭菜园专家 JOI 先生在他的家庭菜园中种植了一种叫 Joy 草的植物。在他的菜园里,有 NN 个花盆自东向西摆放,编号分别为 1,…,N1, \ldots, N。每个花盆中有一株 Joy 草。

春天到了,JOI 先生注意到 Joy 草如他期望地长出了各种颜色的叶子,但他也发现 Joy 草的生长速度没有他期望的那么快。他查阅了书籍,找到了草的以下特点:

  • Joy 草有三种品种,分别会长出红色、绿色和黄色的叶子。

  • 如果两株同一颜色的 Joy 草紧密相邻,它们的生长速度就会减慢。

因此,JOI 先生决定重新摆放花盆,使得没有两株相邻的 Joy 草颜色相同。

花盆非常沉重,因此 JOI 先生每次只能交换相邻的两个花盆。形式化的说,JOI 先生每次操作可以选择一个 i(1≤i<N)i (1 \le i < N),然后交换花盆 ii 和花盆 i+1i+1。

请编写一个程序,计算最少的交换次数。

输入格式

从标准输入中读取数据。

第一行一个整数 NN。

接下来一行一个长度为 NN 的字符串 SS,每个字符为 R,G,Y 中的一个,表示 Joy 草的颜色。

输出格式

输出数据到标准输出中。

输出一行一个整数,表示完成目标所需的最少操作次数。如果无解,输出 −1-1。

5
RRGYY
2
6
RRRRRG
-1
20
YYGYYYGGGGRGYYGRGRYG
8

数据范围与提示

Subtask # 分值 NN 特殊约定
1 5 N≤15N \le 15 -
2 55 N≤60N \le 60
3 15 - SS 中的字符只有 RR 和 GG
4 25 -

对于所有输入数据,有 1≤N≤4001 \le N \le 400。