AT_joi2024_yo2_c 白色光 2 (White Light 2)

有 $N$ 个灯依次排列成一行，从左到右依次编号为 $1$ 到 $N$。每个灯的颜色可以是红色、绿色或蓝色。灯的颜色由字符串 $S$ 表示，第 $i$ 个灯的颜色由 $S$ 的第 $i$ 个字符确定，若该字符为 `R`，则是红色，若为 `G`，则为绿色，若为 `B`，则为蓝色。最开始所有的灯都是亮着的。 JOI 君可以只要还有至少一个灯是亮着的，就可以按照任意顺序，任意次进行以下三种操作。也可以一次操作都不进行。 - 支付 $A$ 日元，将当前所有点亮的灯中最左边的一个熄灭。 - 支付 $B$ 日元，将当前所有点亮的灯中最右边的一个熄灭。 - 支付 $C$ 日元，选择一个任意亮着的灯，将其点亮成任意一种颜色。 JOI 君希望远看这排灯时能呈现出漂亮的白色，因此需要保证亮着的灯颜色从左到右依次为 `RGBRGB...RGB`，即严格的 `RGB` （红绿蓝）循环。不存在亮着的灯时，也认为达成了 `RGB` 循环。像 `GBRGBR` 或 `RGBRG` 这样的排列不满足条件。 现给出灯的初始状态和操作所需的金额，请你编写程序，计算使亮着的灯的颜色排列变为 `RGB` 循环所需要的最小总花费。

输入格式如下： > $N$ $S$ $A$ $B$ $C$

输出使亮着的灯的颜色排列变为 `RGB` 循环所需的最小总花费，不带单位（日元），输出一行。

## 小子任务 1.（4 分）$N = 3$。 2.（22 分）$N \leq 300$。 3.（19 分）$N \leq 10\,000$。 4.（9 分）$N$ 是 $3$ 的倍数，$A = 10^9$，$B = 10^9$，$C = 1$。 5.（10 分）$A = 10^9$，$B = 10^9$，$C = 1$。 6.（36 分）没有额外限制。 ## 样例解释 1 例如如下顺序进行 $4$ 次操作后，点亮的灯颜色排列会成为 `RGB` 循环。用 `-` 表示已熄灭的灯。 1. 支付 $3$ 日元熄灭最左边的第 $1$ 号灯，状态为 `-RBBRG`。 2. 支付 $4$ 日元熄灭最右边的第 $6$ 号灯，状态为 `-RBBR-`。 3. 支付 $4$ 日元熄灭最右边的第 $5$ 号灯，状态为 `-RBB--`。 4. 支付 $5$ 日元把第 $3$ 号灯变成绿色，状态为 `-RGB--`。 无法少于 $16$ 日元实现目标，因此输出 $16$。 这个输入满足小子任务 $2,3,6$ 的约束。 ## 样例解释 2 如下进行 $3$ 次操作后，点亮的灯颜色排列会成为 `RGB` 循环（`-`为熄灭）： 1. 支付 $1$ 日元把第 $2$ 号灯变为绿色，状态为 `BGG`。 2. 支付 $1$ 日元把第 $3$ 号灯变为蓝色，状态为 `BGB`。 3. 支付 $1$ 日元把第 $1$ 号灯变为红色，状态为 `RGB`。 无法少于 $3$ 日元实现，因此输出 $3$。 满足小子任务 $1,2,3,4,5,6$ 的约束。 ## 样例解释 3 如下操作 $3$ 次，点亮的灯颜色排列会变为 `RGB` 循环（`-`表示熄灭）： 1. 支付 $9$ 日元熄灭最左边的第 $1$ 号灯，状态为 `-RB`。 2. 支付 $9$ 日元熄灭最左边的第 $2$ 号灯，状态为 `--B`。 3. 支付 $9$ 日元熄灭最左边的第 $3$ 号灯，状态为 `---`。 无法少于 $27$ 日元实现，因此输出 $27$。注意，当没有任何灯亮着时也认为满足条件。 该输入满足小子任务 $1,2,3,6$。 ## 样例解释 4 当前排列已经是 `RGB` 的循环，因此输出 $0$。 输入满足小子任务 $2,3,4,5,6$。 ## 样例解释 5 输入满足小子任务 $2,3,5,6$。 ## 样例解释 6 输入满足小子任务 $2,3,6$。 ## 数据范围 - $1 \leq N \leq 200\,000$。 - $S$ 是长度为 $N$ 的字符串。 - $S$ 的每个字符是 `R`、`G` 或 `B`。 - $1 \leq A \leq 10^9$。 - $1 \leq B \leq 10^9$。 - $1 \leq C \leq 10^9$。 - $N, A, B, C$ 均为整数。 由 ChatGPT 5 翻译