配点: 100 点
問題文
N 灯从左侧开始水平排列。
它们的编号最大为 1 它们的编号最大为 N 。每个灯的颜色为红色、绿色或蓝色。浅色是字符串 S 和光 i (1 \leqq i \leqq N) 的颜色是S 的
可以考虑 i 第一个字母是
当 R 时为红色,
当G 时呈绿色,B 时为蓝色。最初所有灯都亮着。
JOI 你是点亮的光 1 只要有至少一个,以下 3 您可以按任意顺序执行各种操作,次数不限。操作 1 您不必多次执行此操作。
- A 支付日元即可关闭最左边亮着的灯。
- B 支付日元即可关闭亮着的灯中最右边的灯。
- C 支付日元即可看到点亮的灯 1 选择一种颜色并将其重新打开为您最喜欢的颜色。
JOI 你希望这排灯从远处看时看起来很漂亮的白色。为此,我们需要知道从左侧观察点亮的灯光时颜色的排列。
就像 RGBRGB...RGB 必须重复 RGB(红色、绿色和蓝色)。然而,1 即使没有一直亮着的灯。
它被认为是 RGB 的重复。
请注意,诸如 GBRGBR 呀
我正在使用 RGBRG 之类的颜色序列不满足条件。
给定有关灯的信息以及操作它们所需的资金量,为点亮的灯创建一系列颜色。
编写一个程序来找出重复 RGB 所需的最低金额。
制約
- 1 \leqq N \leqq 200\,000.
- S 是长度 它是一个 N 字符串。
- S 中的每个字符是
R,G,B。 - 1 \leqq A \leqq 10^9.
- 1 \leqq B \leqq 10^9.
- 1 \leqq C \leqq 10^9.
- N, A, B, C 是一个整数。
小課題
- (4 点) N = 3.
- (22 点) N \leqq 300.
- (19 点) N \leqq 10\,000.
- (9 点) N 是 3 的倍数,A = 10^9,B = 10^9,C = 1.
- (10 点) A = 10^9,B = 10^9,C = 1.
- (36 点)没有额外的限制。
入力
输入按以下格式给出。
N S A B C
出力
点亮灯光的颜色排列
计算重复 RGB (不带单位(日元))所需的最小金额。 1 行输出.
入力例 1
6 GRBBRG 3 4 5
出力例 1
16
例如如下 4 执行该操作两次时,点亮的灯光的颜色排列会发生变化。 RGB 将重复。熄灭的灯
由 - 表示。
- 3 支付日元点亮的灯中最左边的灯
关闭 1 。每个灯的状态是一个字符串
-RBBRG表示。 - 4 支付日元点亮的灯中最右边的灯 6 。每个灯的状态是一个字符串
-RBBR-表示。 - 4 支付日元点亮的灯中最右边的灯 5 。每个灯的状态是一个字符串
-RBB--表示。 - 5 支付日元并写
选择 3 并将其重新打开为绿色。每个灯的状态是一个字符串
-RGB--表示。
16 您可以花费不到日元来观看点亮的灯光的颜色排列。 RGB 不能重复,所以16 输出。
此输入示例是一个小作业。 2,3,6 满足约束。 选择
入力例 2
3 BRG 1000000000 1000000000 1
出力例 2
3
例如如下 3 执行该操作两次时,点亮的灯光的颜色排列会发生变化。 RGB 将重复。熄灭的灯
由 - 表示。
- 1 支付日元并写
选择 2 并将其重新打开为绿色。每个灯的状态是一个字符串
BGG表示。 - 1 支付日元并写
选择 3 并将其重新打开为蓝色。每个灯的状态是一个字符串
选择
BGB表示。 - 1 支付日元并写
选择 1 并将其重新亮起为红色。每个灯的状态是一个字符串
RGB表示。
3 您可以花费不到日元来观看点亮的灯光的颜色排列。 RGB 不能重复,所以3 输出。
此输入示例是一个小作业。 1,2,3,4,5,6 满足约束。 选择
入力例 3
3 GRB 9 11 14
出力例 3
27
例如如下 3 执行该操作两次时,点亮的灯光的颜色排列会发生变化。 RGB 将重复。熄灭的灯
由 - 表示。
- 9 支付日元点亮的灯中最左边的灯
关闭 1 。每个灯的状态是一个字符串
-RB表示。 - 9 支付日元点亮的灯中最左边的灯
关闭 2 。每个灯的状态是一个字符串
--B表示。 - 9 支付日元点亮的灯中最左边的灯
关闭 3 。每个灯的状态是一个字符串
---表示。
27 您可以花费不到日元来观看点亮的灯光的颜色排列。 RGB 不能重复,所以27 输出。1 请注意,即使没有常亮的灯,也满足条件。
此输入示例是一个小作业。 1,2,3,6 满足约束。 选择
入力例 4
9 RGBRGBRGB 1000000000 1000000000 1
出力例 4
0
灯光的颜色排列已经 RGB 被重复,所以0 输出。
此输入示例是一个小作业。 2,3,4,5,6 满足约束。 选择
入力例 5
20 BRGBRGBBGBBBGRRBBBRB 1000000000 1000000000 1
出力例 5
2000000008
此输入示例是一个小作业。 2,3,5,6 满足约束。 选择
入力例 6
23 BBGRGBBBBBBGRRGGGGBGGGG 786820955 792349124 710671229
出力例 6
10107224827
此输入示例是一个小作业。 2,3,6 满足约束。 选择