MathBot's blog

By MathBot, history, 6 weeks ago, In English

Source: https://www.e-olymp.com/en/contests/13183/problems/125680 Boyan is playing a computer game. In the beginning there are n balls arranged in a line. Each ball has a number written on it, so that every two consecutive balls have different numbers. The game consists of the following steps:

The player removes a ball from the line.

While there are consecutive balls with equal numbers, they are automatically removed from the line.

If there are balls left in the line, go to step 1, otherwise the game ends.

The score is the number of balls that are automatically removed. The goal of the game is to maximize the score.

Boyan removes the ball with number 3. The balls left are {1, 2, 2, 1, 5}.

Removing the consecutive balls with equal numbers we have {1, 2, 2, 1, 5} -> {1, 1, 5} -> {5}. The ball left is {5}.

Since there are balls left, we go to step 1.

Next iteration:

Boyan removes the ball with number 5. The balls left are {}.

There are no consecutive balls with equal numbers.

There are no balls left, so the game ends.

The number of balls that are automatically removed is 4. It is the maximum possible score for this game. Boyan is playing a lot, but he is still not sure when he is playing optimally. Write program game to help him to find the best score he can achieve.

Input The first line contains the positive integer n (1 ≤ n ≤ 500). The second line contains n positive integers — the numbers written on the balls (number on a ball ≤ 106).

Output Print the maximum possible score Boyan can achieve.

 
 
 
 
  • Vote: I like it
  • +10
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

You should provide source of the problem. It helps to verify that it is not from an ongoing contest, and also helps others understand the problem better.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by MathBot (previous revision, new revision, compare).

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Help!