← 返回题目列表

AtCoder · joi2024_yo2_c

C. 白光2

中文机器翻译题面 查看原题

配点: 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 是一个整数。

小課題

  1. (4 点) N = 3.
  2. (22 点) N \leqq 300.
  3. (19 点) N \leqq 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 点)没有额外的限制。

入力

输入按以下格式给出。

N
S
A B C

出力

点亮灯光的颜色排列 计算重复 RGB (不带单位(日元))所需的最小金额。 1 行输出.


入力例 1

6
GRBBRG
3 4 5

出力例 1

16

例如如下 4 执行该操作两次时,点亮的灯光的颜色排列会发生变化。 RGB 将重复。熄灭的灯 由 - 表示。

  1. 3 支付日元点亮的灯中最左边的灯 关闭 1 。每个灯的状态是一个字符串 -RBBRG 表示。
  2. 4 支付日元点亮的灯中最右边的灯 6 。每个灯的状态是一个字符串 -RBBR- 表示。
  3. 4 支付日元点亮的灯中最右边的灯 5 。每个灯的状态是一个字符串 -RBB-- 表示。
  4. 5 支付日元并写 选择 3 并将其重新打开为绿色。每个灯的状态是一个字符串 -RGB-- 表示。

16 您可以花费不到日元来观看点亮的灯光的颜色排列。 RGB 不能重复,所以16 输出。

此输入示例是一个小作业。 2,3,6 满足约束。 选择


入力例 2

3
BRG
1000000000 1000000000 1

出力例 2

3

例如如下 3 执行该操作两次时,点亮的灯光的颜色排列会发生变化。 RGB 将重复。熄灭的灯 由 - 表示。

  1. 1 支付日元并写 选择 2 并将其重新打开为绿色。每个灯的状态是一个字符串 BGG 表示。
  2. 1 支付日元并写 选择 3 并将其重新打开为蓝色。每个灯的状态是一个字符串 选择 BGB 表示。
  3. 1 支付日元并写 选择 1 并将其重新亮起为红色。每个灯的状态是一个字符串 RGB 表示。

3 您可以花费不到日元来观看点亮的灯光的颜色排列。 RGB 不能重复,所以3 输出。

此输入示例是一个小作业。 1,2,3,4,5,6 满足约束。 选择


入力例 3

3
GRB
9 11 14

出力例 3

27

例如如下 3 执行该操作两次时,点亮的灯光的颜色排列会发生变化。 RGB 将重复。熄灭的灯 由 - 表示。

  1. 9 支付日元点亮的灯中最左边的灯 关闭 1 。每个灯的状态是一个字符串 -RB 表示。
  2. 9 支付日元点亮的灯中最左边的灯 关闭 2 。每个灯的状态是一个字符串 --B 表示。
  3. 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 满足约束。 选择