MNYC '17: Removing Christmas Trees

View as PDF

Submit solution

All submissions

Best submissions

Points: 15 (partial)

Time limit: 1.0s

Memory limit: 64M

Author:

Daniel123

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$ $N$ Christmas trees in a row. The $i^\text{th}$ $i^{th}$ Christmas tree is labelled with a number $n_i$ $n_{i}$ $(1 \le n_i \le N)$ $(1 \leq n_{i} \leq 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}$ $l^{th}$ to $r^\text{th}$ $r^{th}$ Christmas trees, the $(l-1)^\text{th}$ $(l - 1)^{th}$ Christmas tree will now be adjacent to the $(r+1)^\text{th}$ $(r + 1)^{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?

Constraints

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

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

Input Specification

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

Output Specification

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

Sample Input 1

Copy

5
1 2 3 2 1

Sample Output 1

Copy

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

Copy

5
1 1 1 1 1

Sample Output 2

Copy

Comments

0

onlyIfStatement commented on Jan. 8, 2017, 12:32 a.m. ← edited →

What is $N$ $N$ without constraints?

0

Daniel123 commented on Jan. 8, 2017, 3:09 a.m.

$1 \le N \le 1000$ $1 \leq N \leq 1000$

-7

onlyIfStatement commented on Jan. 8, 2017, 4:17 p.m. ← edited →

it says that's for 90%

oh 10% + 90%, okay

This comment is hidden due to too much negative feedback. Show it anyway.