P1541 [NOIP 2010 Senior] Turtle Chess

NOIP 2010 Senior T2.

On Xiaoming’s birthday, his father gave him a Turtle Chess set as a gift. The Turtle Chess board is a row of $N$ cells, each with a score (a non-negative integer). Cell $1$ is the only starting point, and cell $N$ is the end. The player controls a turtle piece to move from the start to the end. There are $M$ crawling cards in Turtle Chess, divided into $4$ different types (the $M$ cards do not necessarily include all $4$ types; see the sample). Each type of card is labeled with one of the numbers $1,2,3,4$, meaning that after using such a card, the turtle moves forward by the corresponding number of cells. In the game, each time the player must choose one crawling card that has not been used before from all cards, and move the turtle forward accordingly. Each card can be used only once. In the game, the turtle automatically gains the score of the starting cell, and during subsequent moves, whenever it arrives at a cell, it gains that cell’s score. The final score is the sum of the scores of all cells the turtle visits from start to end. Clearly, different orders of using the crawling cards can lead to different final scores. Xiaoming wants to find an order that maximizes the final score. Given the score of each board cell and all the crawling cards, can you tell Xiaoming the maximum score he can obtain?

Numbers on each line are separated by a single space. The first line contains two positive integers $N,M$, the number of board cells and the number of crawling cards. The second line contains $N$ non-negative integers, $a_1,a_2,…,a_N$, where $a_i$ is the score on cell $i$. The third line contains $M$ integers, $b_1,b_2,…,b_M$, which are the numbers on the $M$ crawling cards. The input guarantees that upon reaching the end, exactly all $M$ crawling cards have been used.

Output one integer, the maximum score Xiaoming can obtain.

Each test point: 1 s. Xiaoming uses the crawling cards in the order $1,1,3,1,2$, and the score is $6+10+14+8+18+17=73$. Note that since the start is $1$, he automatically gains the score $6$ on cell $1$. Constraints: For $30\%$ of the testdata, $1 \le N \le 30,1 \le M \le 12$. For $50\%$ of the testdata, $1 \le N \le 120,1 \le M \le 50$, and among the $4$ types of crawling cards, the count of each type does not exceed $20$. For $100\%$ of the testdata, $1 \le N \le 350,1 \le M \le 120$, and among the $4$ types of crawling cards, the count of each type does not exceed $40$；$0 \le a_i \le 100(1 \le i \le N),1 \le b_i \le 4(1 \le i\le M)$。 Translated by ChatGPT 5