[JOI 2019 Final]たのしいたのしいたのしい家庭菜園

题目背景

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

题目描述

家庭菜园专家 JOI 先生在他的家庭菜园中种植了一种叫 Joy 草的植物。在他的菜园里，有 $N$ 个花盆自东向西摆放，第 $i$ 个编号为 $i$。每个花盆中有一株 Joy 草。

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

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

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

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

花盆非常沉重，因此 JOI 先生每次只能交换相邻的两个花盆。形式化的说，JOI 先生每次操作可以选择一个 $i$，然后交换花盆 $i$ 和花盆 $i+1$。

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

输入格式

第一行一个整数 $N$。

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

输出格式

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

样例 #1

样例输入 #1

5
RRGYY

样例输出 #1

2

样例 #2

样例输入 #2

6
RRRRRG

样例输出 #2

-1

样例 #3

样例输入 #3

20
YYGYYYGGGGRGYYGRGRYG

样例输出 #3

8

提示

样例解释 $1$:

一种合法的方案是：

第一步：交换第三个花盆和第四个花盆。

第二步：交换第二个花盆和第三个花盆。

可以证明，不存在次数更少的方案

样例解释 $2$：

可以证明，无论如何移动，均不可达到目标。

对于 $5\%$ 的数据，$N\le 15$。

对于 $60\%$ 的数据，$N\le 60$。

另有 $15\%$ 的数据，字符串仅包含 R,G。

对于 $100\%$ 的数据，$N\le 400$。

题解：

#include <bits/stdc++.h>

using namespace std;

char S[444];
int dp[444][444][444][3];
int RG[444], RY[444], GY[444], GR[444], YR[444], YG[444];
int n, r, g, y;

int main(){
	int i, j, k;

	scanf("%d%s", &n, S);

	for(i=0; i<n; i++){
		if(S[i] == 'R') RG[++r] = g ,RY[r] = y;
		else if(S[i] == 'G') GY[++g] = y, GR[g] = r;
		else YR[++y] = r, YG[y] = g;
	}

	for(i=0; i<=r; i++){
		for(j=0; j<=g; j++){
			for(k=0; k<=y; k++){
				dp[i][j][k][0] = i? min(dp[i - 1][j][k][1], dp[i - 1][j][k][2]) + max(0, RG[i] - j) + max(0, RY[i] - k) : (i + j + k != 0) * 1e9;
				dp[i][j][k][1] = j? min(dp[i][j - 1][k][2], dp[i][j - 1][k][0]) + max(0, GY[j] - k) + max(0, GR[j] - i) : (i + j + k != 0) * 1e9;
				dp[i][j][k][2] = k? min(dp[i][j][k - 1][0], dp[i][j][k - 1][1]) + max(0, YR[k] - i) + max(0, YG[k] - j) : (i + j + k != 0) * 1e9;
			}
		}
	}

	k = min(min(dp[r][g][y][0], dp[r][g][y][1]), dp[r][g][y][2]);
	printf("%d\n", k < 1e9? k : -1);

	return 0;
}