P7414 [USACO21FEB] Modern Art 3 G

Tired of ordinary two-dimensional paintings (and also feeling upset because her work has been copied by others), the great cow artist Cowcasso decided to switch to a more minimalist one-dimensional style. Her latest painting can be described by a one-dimensional array of length $N$ ($1 \leq N \leq 300$), where each color is represented by an integer in $1 \ldots N$. To Cowcasso’s frustration, her rival Moooo-net seems to have figured out how to copy these one-dimensional paintings anyway. Moooo-net paints an interval with one color, waits for the paint to dry, then paints another interval, and so on. Moooo-net may use each of the $N$ colors any number of times (or not at all). Compute the minimum number of painting operations Moooo-net needs in order to copy Cowcasso’s latest one-dimensional painting.

The first line contains $N$. The next line contains $N$ integers in the range $1 \ldots N$, representing the color of each cell in Cowcasso’s latest one-dimensional painting.

Output the minimum number of painting operations needed to copy this painting.

#### Explanation for Sample 1: In this sample, Moooo-net can paint as follows. We use $0$ to represent an unpainted cell. - Initially, the entire array is unpainted: `0 0 0 0 0 0 0 0 0 0` - Moooo-net paints the first nine cells with color $1$: `1 1 1 1 1 1 1 1 1 0` - Moooo-net paints an interval with color $2$: `1 2 2 2 2 2 2 2 1 0` - Moooo-net paints an interval with color $3$: `1 2 3 3 3 3 3 2 1 0` - Moooo-net paints an interval with color $4$: `1 2 3 4 4 4 3 2 1 0` - Moooo-net paints one cell with color $1$: `1 2 3 4 1 4 3 2 1 0` - Moooo-net paints the last cell with color $6$: `1 2 3 4 1 4 3 2 1 6 ` Note that in the first operation, Moooo-net could also paint the tenth cell with color $1$ at the same time as the first nine cells; this would not affect the final result. #### Testdata Properties: - For an additional $15\%$ of the testdata, only colors $1$ and $2$ appear in the painting. - For an additional $30\%$ of the testdata, for each $1 \le i \le N$, the color of the $i$-th cell lies in the range $\left[12\left\lfloor\frac{i-1}{12}\right\rfloor+1,12\left\lfloor\frac{i-1}{12}\right\rfloor+12\right]$. - For an additional $50\%$ of the testdata, there are no additional constraints. Problem by: Brian Dean, Benjamin Qi Translated by ChatGPT 5