Tetris-Like Game
Time limit1sMemory limit128 MB
Given a score table for consecutive-letter group sizes, decide optimally which of three stack-like columns to drop each incoming letter into to maximize the total column score.
- Level
Hard8 of 10
- Topics
- Dynamic programming, Implementation, Greedy
- Solved
- No attempts yet
Problem
Sunyoung is playing a Tetris-like game with three empty columns.
During the game, letters appear one by one at the top of the screen. Whenever a letter appears, Sunyoung chooses one of the three columns. If the chosen column is empty, the letter is placed at the bottom of that column; otherwise, it is placed on top of the current top letter of that column.
After the game ends, the final score is the sum of the scores of the three columns. The score of one column is computed as follows.
First, find every group of adjacent equal letters in that column. Suppose one column contains the following letters.
A
A
A
B
C
C
C
A
A
This column has 4 groups in total. The score of the column is the sum of the scores assigned to the sizes of those groups.
For instance, if a group of size 1 is worth 3 points, a group of size 2 is worth 7 points, and a group of size 3 is worth 5 points, then the column above scores 5 + 3 + 5 + 7 = 20 points.
You are given the score for each group size and the order in which the letters appear. Find the maximum score Sunyoung can obtain.
Input
The first line contains five natural numbers B1, B2, B3, B4, and B5. For i = 1, 2, 3, 4, Bi is the score of a group made of i letters, and B5 is the score of a group made of 5 or more letters. Each of the five numbers is at most 100.
The second line contains N, the number of letters that appear on the screen. (1 <= N <= 1000)
The third line contains the N letters in the order they appear. Each letter is an uppercase English letter.
Output
Print the maximum score Sunyoung can obtain on the first line.