Board Game
Time limit1sMemory limit128 MB
Given a colored card sequence and a colored graph, find a walk starting at village 1 that uses cards in order to maximize color matches with traversed roads.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Graph, Implementation
- Solved
- No attempts yet
Problem
A player starts with N cards. The front of the cards is numbered from 1 to N in order, and the back of each card is colored red (R), green (G), or blue (B).
The player starts in village 1. On each move, the player must move from the current village to an adjacent village connected by a road, and must use the remaining card with the smallest number. Each road is also colored R, G, or B. If the color of the used card matches the color of the road taken, the player earns 10 points. The same village or road may be visited multiple times.
Find the maximum score obtainable after using all cards in numbered order.
Input
The first line contains the number of cards N. The second line contains the colors of the N cards in numbered order, separated by spaces.
The third line contains the number of villages M and the number of roads K, separated by a space. Each of the next K lines contains the two endpoint village numbers of a road and the road color, separated by spaces.
There is at most one road directly connecting any pair of villages. N is a positive integer at most 1,000, M is a positive integer at most 500, and K is a positive integer at most 10,000. Every card color and road color is one of R, G, and B.
Output
Print the maximum score obtainable in the board game on the first line.