Song
Time limit1sMemory limit256 MB
Given a 26 by 26 pair score table, pick an L-note song starting from C that maximizes the sum of adjacent pair scores.
- Level
Medium7 of 10
- Topics
- Dynamic programming, Matrix, Graph
- Solved
- No attempts yet
Problem
A rabbit instrument has 26 notes, written with the uppercase English letters A to Z. Writing these letters in a row gives a rabbit song, and one letter means playing that note for one beat. The length of a song is the number of letters. For example, AASDFG is a song of length 6: beat 1 plays A, beat 2 plays A, beat 3 plays S, beat 4 plays D, beat 5 plays F, and beat 6 plays G.
A rabbit psychologist found that the happiness of the note on beat is decided by the pair made of the note on beat and the note on beat . The values sit in a note happiness table, and the table differs from rabbit to rabbit. A row of the table is the note on beat and a column is the note on beat , both in order from A to Z. Write for the value in row and column . The note on beat 1 gives no happiness, so the song AASDFG gives happiness .
You are given a note happiness table, the first note of a song, and the length of the song. Find the largest happiness such a song can give.
Input
The first line has the number of test cases (). Each test case is made of the following.
- The note happiness table, given on 26 lines. Each line has 26 happiness values separated by spaces (). The -th value on the -th line is the happiness of playing the -th note right after the -th note, and the notes run from A to Z.
- The next line has the number of questions ().
- Each of the next lines has an uppercase English letter , the first note of the song, and the length of the song, separated by a space ().
Output
For each question, print the largest happiness of a song of length that starts with the note . Print one value per line, in the order the questions are given.