NC222437. [USACOFeb2021G]ModernArt3

描述

输入描述

The first line of input contains N.
The next line contains N integers in the range 1…N indicating the color of each cell in Picowso's latest 1-dimensional painting.

输出描述

Output the minimum number of brush strokes needed to copy the painting.

示例1

输入:

10
1 2 3 4 1 4 3 2 1 6

输出:

6

说明:

In this example, Moonet may paint the array as follows. We denote an unpainted cell by 0.

Initially, the entire array is unpainted:

0 0 0 0 0 0 0 0 0 0 

Moonet paints the first nine cells with color 11:

1 1 1 1 1 1 1 1 1 0 

Moonet paints an interval with color 22:

1 2 2 2 2 2 2 2 1 0 

Moonet paints an interval with color 33:

1 2 3 3 3 3 3 2 1 0 

Moonet paints an interval with color 44:

1 2 3 4 4 4 3 2 1 0 

Moonet paints a single cell with color 11:

1 2 3 4 1 4 3 2 1 0 

Moonet paints the last cell with color 66:

1 2 3 4 1 4 3 2 1 6 

Note that during the first brush stroke, Moonet could have painted the tenth cell with color 11 in addition to the first nine cells without affecting the final state of the array.

原站题解