【JOI2019 Final】有趣的家庭菜园3

题意描述

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

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

• Joy 草有三种品种，分别会长出红色、绿色和黄色的叶子。
• 如果两株同一颜色的 Joy 草紧密相邻，它们的生长速度就会减慢。

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

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

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

---

输入格式

第一行一个整数 $N$。

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

---

输出格式

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

---

Input & Output ‘s examples

Input ‘s eg 1

5
RRGYY

Output ‘s eg 1

2

Input ‘s eg 2

6
RRRRRG

Output ‘s eg 2

-1

Input ‘s eg 3

20
YYGYYYGGGGRGYYGRGRYG

Output ‘s eg 3

8

---

数据范围和约定

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

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

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

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

---

分析

看到 $n \leq 400$ 的数据范围很容易猜到高维 $\text{dp}$。

将三种颜色分别换成 $0 / 1 / 2$，则可以设 $f[i][j][k][0 / 1 / 2]$ 表示当前有 $i$ 个颜色0，$j$ 个颜色1，$k$ 个颜色2的最小交换次数。

显然，每一个状态都可以从上一个状态转移过来，例如：

$$f[i][j][k][0] = f[i - 1][j][k][0/1/2] + cost$$

其他的都同理。

考虑如何快速计算 $cost$，设 $p[0 / 1 / 2][i]$ 表示颜色 $0 / 1 / 2$ 在序列中出现的第 $i$ 次的位置，$g[A][B][i][j] (A,B \in \lbrack 0 , 2 \rbrack)$ 为第 $i$ 个颜色 $A$ 的后边有前 $j$ 个颜色 $B$ 中的多少个颜色 $B$ 出现。则有：

$$g[A][B][i][j] = g[A][B][i][j - 1] + (p[A][i] < p[B][j])$$

而颜色 $A$ 转移的贡献为除颜色 $A$ 以外的另外两种颜色的 $g$ 值之和。可以在预处理 $g$ 数组后直接进行查询。

预处理复杂度为 $O(n^2)$，总时间复杂度为 $O(n^3)$，可以通过本题。

细节部分详见代码。

---

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <climits>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define fi first
#define se second
#define pb push_back
#define MP make_pair
#define PII pair<int , int>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

typedef long long ll;
typedef unsigned long long ull;

template <class T>
inline void read(T &x) {
    char c = getchar(), f = 0; x = 0;
    while (!isdigit(c)) f = (c == '-'), c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    x = f ? -x : x;
}

using namespace std;

const int N = 10000 + 5;
const int M = 405 + 5;
const int HA = 998244353;

int n , s[M] , pla[3][M] , tot[3]; 
char str[M];

int g[3][3][M][M] , f[M][M][M][3];

int cost(int col , int x , int y , int z) {
    int res = 0 , tp = 0;
    rep(i , 0 , 2) {
        if(i != col) {
            tp ++;
            if(tp & 1) res += g[col][i][x][y];
            else res += g[col][i][x][z];
        }
    }
    return res;
}

void upd(int &x , int y) { x = min(x , y); }

#define LOCAL

int main() {
    #ifdef LOCAL
        freopen("b.in" , "r" , stdin);
        freopen("b.out" , "w" , stdout);
    #endif
    read(n);
    scanf("%s" , str + 1);
    rep(i , 1 , n) {
        if(str[i] == 'R') s[i] = 0;
        if(str[i] == 'G') s[i] = 1;
        if(str[i] == 'Y') s[i] = 2;
        pla[s[i]][++ tot[s[i]]] = i;
    }
    rep(op , 0 , 2) {
        rep(op2 , 0 , 2) {
            if(op == op2) continue;
            rep(i , 1 , tot[op]){
                rep(j , 1 , tot[op2]) {
                    g[op][op2][i][j] = g[op][op2][i][j - 1] + (pla[op][i] < pla[op2][j]);
                }
            }
        }
    }
    clean(f , 0x3f);
    int ans = 0x3f3f3f3f;
    rep(i , 0 , 2) f[0][0][0][i] = 0;
    rep(i , 0 , tot[0]) {
        rep(j , 0 , tot[1]) {
            rep(k , 0 , tot[2]) {
                if(i) rep(sta , 0 , 2) if(sta != 0) upd(f[i][j][k][0] , f[i - 1][j][k][sta] + cost(0 , i , j , k));
                if(j) rep(sta , 0 , 2) if(sta != 1) upd(f[i][j][k][1] , f[i][j - 1][k][sta] + cost(1 , j , i , k));
                if(k) rep(sta , 0 , 2) if(sta != 2) upd(f[i][j][k][2] , f[i][j][k - 1][sta] + cost(2 , k , i , j));
            }
        }
    }
    rep(i , 0 , 2) ans = min(ans , f[tot[0]][tot[1]][tot[2]][i]);
    printf("%d\n" , ans == 0x3f3f3f3f ? -1 : ans);
    
    return 0;
}

---

THE END