← 返回题目列表

AtCoder · arc010_3

C. 堆叠拼图

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

問題文

有一天,高桥决定玩以下游戏。
m 色块 n 個、1 他们会一个接一个地倒下。
1 每次有方块掉落时,高桥都可以选择捡起它并堆放在堆上,或者直接扔掉而不堆放。
一堆方块是 1 块必须放置在堆的顶部。
所有方块倒塌后,所得山体的评估如下。
  • 颜色奖励:每种颜色的分数根据该堆中包含的件数给出。
  • 组合奖励:相同颜色的方块 如果连续堆叠 x ,将分配连击奖励积分。 根据 Y 将奖励 Y×(x-1) 积分。
  • 所有颜色奖励:在山上 m 每个色块 如果它包含超过 1 如果它包含超过 Z 积分。
给定下落块的类型和顺序,以及评估每座山的分数分配,找到评估中可以获得的最高分数。

入力

输入是按以下格式从标准输入给出的。
n m Y Z
c_1 p_1
c_2 p_2
:
:
c_m p_m
b_1b_2 ‥‥ b_n
  • 1 线 n, m, Y, Z 由半角空格分隔。
    1. n 是块数 1≦n≦5,000 很满意。 当
    2. m 是块中颜色的总数 1≦m≦10 很满意。 当
    3. Y 是连击奖励积分分配 -100≦Y≦100 很满意。 当
    4. Z 所有颜色都有奖励积分。 -10,000≦Z≦10,000 很满意。 当
    5. n, m, Y, Z 均为整数。 来自行
  • 2 从线 m+1 至行 在 m 行给出了每个颜色的奖励分数。
    1. c_i 是 i(1≦i≦m) 这是给定块的颜色。 这是
    2. p_i 是 c_i 的颜色奖励分布。
    3. c_i 是一个大写字母 (A-Z)、p_i 是 -100≦p_i≦100 很满意。 当
    4. 不会授予重复积分 (x≠y 如果 c_x≠c_y)
  • m+2 第一行显示了表示方块下落顺序的长度。 给出了字符串 n 。
    1. b_j 是 j(1≦j≦n) 代表掉落方块的颜色。
    2. b_j 是 c_1,c_2,...,c_m 。

出力

评估中可以获得的最高分数作为标准输出输出。 输出为 1 行。
请在末尾输出换行符。

入力例 1

5 3 3 5
R 1
G 1
B 1
RGBRR

出力例 1

13
  • 当所有的方块都堆满后,
    • 颜色奖励:每种颜色都有一个点分布。 1 点,所以1 点 × 5 個 = 5点
    • 连击奖励:R 由于 2 是连续的,3×(2-1)=3 点
    • 所有颜色奖励:所有颜色 1 堆积的不止一堆,所以5 点
    根据5+3+5=13 积分。
  • 如果你丢弃任何一个方块,分数就会低于这个,所以答案是 13 点。

入力例 2

3 3 3 5
R 1
G 3
B 2
RBR

出力例 2

5
  • 当所有的方块都堆满后,
    • 颜色奖励:1 点 ×2 個 +2 点 ×1 個 =4 点
    • 由于不连续,所以组合加值是,并且由于不包括G,所以所有颜色的加值是各 0 点
    根据4 点。
  • 但是,如果你扔掉B并堆积RR,
    • 颜色奖励:1 点 ×2 個 =2 点
    • 组合奖励:3×(2-1)=3 点
    在,5 点是最高分。 按照

入力例 3

8 3 5 3
R 1
G 1
B 1
RRGRRBRR

出力例 3

31
  • 図 (a) 的顺序 8 方块将会掉落。
  • 当所有的方块都堆满后,图 就像 (b) ,2 组合 3 可以组合。
  • 此外,所有颜色奖励都包含在内,所以1 点 × 8 個 + 5 点 × (2-1) × 3 組 + 3 点 = 26 点。
  • 然而,图。 如果只将 R 堆成 (c) 那样的堆,1 点 × 6 個 + 5 点 × (6-1) + 0 点 = 31 点。
  • 当堆中只有R堆时,将是最高分,31 就是答案。

入力例 4

8 3 5 3
R 1
G 100
B 1
RRGRRBRR

出力例 4

126
  • 满载时(图 1) (a)):107 点 + 5 点 × (2-1) × 3 組 + 3 点 = 125 点
  • 仅加载 R 时(图 1) (b)):6 点 + 5 点 × (6-1) + 0 点 = 31 点
  • 加载 B 以外的项目时(图 1) (c)):106 点 + 5 点 × \{(2-1) + (4-1)\} + 0 点 = 126 点
  • 因此,最高分是 126 点。