MNYC '17: Removing Christmas Trees

View as PDF

Submit solution

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 N christmas trees in a row. The i^\text{th} christmas tree is labelled with a number n_i (1 \le n_i \le N). 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 l^\text{th} to r^\text{th} christmas trees, the (l-1)^\text{th} christmas tree will now be adjacent to the (r+1)^\text{th} 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 N, the number of christmas trees.
The next line contains N space separated integers, the labels of the christmas trees.

Constraints

For 10\% of the points, 1 \le N \le 5.

For 90\% of the points, 1 \le N \le 1000.

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

Comments


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

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


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

    What is N without constraints?


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

      1 \le N \le 1000