MNYC '17: Removing Christmas Trees

View as PDF

Submit solution


Points:15 (partial)
Time limit:2.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 Specifications

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


  • -16
    Cole_Hafkenscheid
     commented on Jan. 10, 2017
    asd

    meh


  • 0
    onlyIfStatement
     commented on Jan. 7, 2017
    N without constraints?

    What is N without constraints?


    • 0
      Daniel123
       commented on Jan. 7, 2017

      1 \le N \le 1000


      • -2
        onlyIfStatement
         commented on Jan. 8, 2017 edited

        it says that's for 90%

        oh 10% + 90%, okay