## MNYC '17: Removing Christmas Trees

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

Since Christmas is over, and Arstin's neighbour, Justharva, is back home from vacation, Arstin needs to remove all of his christmas trees from Justharva's front yard. There are christmas trees in a row. The christmas tree is labelled with a number . Some trees will have the same label.

In one move, Arstin can remove up to as many christmas trees which all have the same label and are contiguous. If Arstin removes the to christmas trees, the christmas tree will now be adjacent to the christmas tree.

Arstin wants to remove all of his christmas trees in the least amount of moves. Can you write a program to help him determine the least amount of moves it will take him to remove all of his christmas trees?

#### Input Specification

The first line contains the integer , the number of christmas trees.
The next line contains space separated integers, the labels of the christmas trees.

##### Constraints

For of the points, .

For of the points, .

#### Output Specification

Output the minimum amount of moves it would take Arstin to remove all of his christmas trees.

#### Sample Input 1

5
1 2 3 2 1

#### Sample Output 1

3

#### Explanation for Sample Output 1

If Arstin were first to remove the tree labelled with a '3', the two trees labelled with '2' will become adjacent and Arstin can move them both in 1 move. Then the two trees labelled with '1', will become adjacent and Arstin can remove them with one move. There will be a total of 3 moves.

#### Sample Input 2

5
1 1 1 1 1

#### Sample Output 2

1

• commented on Jan. 10, 2017, 10:48 a.m.

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on Jan. 7, 2017, 7:32 p.m.

What is N without constraints?

• commented on Jan. 7, 2017, 10:09 p.m.

• commented on Jan. 8, 2017, 11:17 a.m. edited

it says that's for 90%

oh 10% + 90%, okay