레이팅 미적용평범한 2차원 미술 작품에 싫증이 난 데다 (자신의 작품을 남들이 베끼는 것에도 화가 난) 위대한 소 예술가 피카우소는 더 미니멀한 1차원 스타일로 전환하기로 했다. 그녀의 최신 그림은 길이 \(N\)(\(1 \leq N \leq 300\))의 1차원 색상 배열로 표현할 수 있으며, 각 색상은 \(1\ldots N\) 범위의 정수로 지정된다.
피카우소에게 매우 실망스럽게도, 경쟁자 무네는 이런 1차원 그림마저 베끼는 방법을 알아낸 것 같다! 무네는 하나의 구간을 하나의 색으로 칠하고, 마를 때까지 기다린 뒤, 또 다른 구간을 칠하는 식으로 작업한다. 무네는 \(N\)가지 색 각각을 원하는 만큼 (전혀 쓰지 않아도 된다) 사용할 수 있다.
무네가 피카우소의 최신 1차원 그림을 베끼는 데 필요한 붓질의 횟수를 계산하라.
문제 제공: Brian Dean, Benjamin Qi
채점 방식
- 테스트 케이스 2-4에서는 그림에 색 \(1\)과 \(2\)만 나타난다.
- 테스트 케이스 5-10에서는 각 \(1\le i\le N\)에 대해 \(i\)번째 칸의 색이 \(\left[12\left\lfloor\frac{i-1}{12}\right\rfloor+1,12\left\lfloor\frac{i-1}{12}\right\rfloor+12\right]\) 범위에 있다.
- 테스트 케이스 11-20은 추가 제약이 없다.
문제 제공: Brian Dean, Benjamin Qi
입력의 첫째 줄에 \(N\)이 주어진다.
다음 줄에 피카우소의 최신 1차원 그림의 각 칸의 색을 나타내는, \(1 \ldots N\) 범위의 정수 \(N\)개가 주어진다.
그림을 베끼는 데 필요한 붓질의 최소 횟수를 출력한다.
10
1 2 3 4 1 4 3 2 1 66In 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 \(1\):
1 1 1 1 1 1 1 1 1 0
- Moonet paints an interval with color \(2\):
1 2 2 2 2 2 2 2 1 0
- Moonet paints an interval with color \(3\):
1 2 3 3 3 3 3 2 1 0
- Moonet paints an interval with color \(4\):
1 2 3 4 4 4 3 2 1 0
- Moonet paints a single cell with color \(1\):
1 2 3 4 1 4 3 2 1 0
- Moonet paints the last cell with color \(6\):
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 \(1\) in addition to the first nine cells without affecting the final state
of the array.
riseoj 작성
출처 올림피아드 > USACO > 2020-2021 > February > Gold