AtCoder Regular Contest 010

C - 積み上げパズル


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 64MB

問題文

高橋君はある日、以下のようなゲームで遊ぶことにしました。
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_ii(1≦i≦m) 番目に与えられるブロックの色である。
    2. p_ic_i に対する色ボーナスの配点である。
    3. c_i は英大文字(A-Z)、p_i-100≦p_i≦100 を満たす。
    4. 配点は重複して与えられない(x≠y ならば c_x≠c_y)
  • m+2 行目には落ちてくるブロックの順序を表す長さ n の文字列が与えられる。
    1. b_jj(1≦j≦n) 番目に落ちてくるブロックの色を表している。
    2. b_jc_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 点です。
  • しかし、図 (c) のようにRのみを山に積むと、1 点 × 6 個 + 5× (6-1) + 0= 31 点になります。
  • Rだけ山に積むとき最高得点となり、31 が答えです。

入力例 4

8 3 5 3
R 1
G 100
B 1
RRGRRBRR

出力例 4

126
  • 全部積んだ場合(図 (a)):107 点 + 5× (2-1) × 3+ 3= 125
  • Rのみを積んだ場合(図 (b)):6 点 + 5× (6-1) + 0= 31
  • B以外を積んだ場合(図 (c)):106 点 + 5× \{(2-1) + (4-1)\} + 0= 126
  • したがって、最高得点は 126 点です。

Submit提出する