Problem
Chloe는 최근 휴대폰에 Zuma를 설치했습니다. 플레이어에게 n개의 보석 행이 주어지며, 그 중 i번째는 c
i 색상을 가집니다. 게임의 목적 – 가능한 한 몇 초 안에 모든 돌을 파괴하십시오.
1초 안에 Chloe는 회문인 하위 문자열(인접한 돌의 시퀀스)을 선택하고 삭제할 수 있습니다. 이 하위 문자열을 제거한 후 나머지 돌은 다시 연속적인 행을 형성하도록 이동됩니다. 전체 라인을 파괴하는 데 필요한 최소 시간(초)은 무엇입니까?
문자열(또는 하위 문자열)은 왼쪽에서 오른쪽으로 읽는 것과 오른쪽에서 왼쪽으로 읽는 것이 같으면 회문(palindrome)입니다. 이 경우 이것은 첫 번째 돌의 색이 마지막 돌의 색과 같고, 두 번째 색이 두 번째 돌의 색과 같다는 것을 의미합니다.
입력:
입력의 첫 번째 줄에는 단일 정수 n(1 ≤ n ≤ 500)이 포함됩니다. 초기 행의 스톤 수.
두 번째 줄은 n개의 정수를 포함하며 그 i번째는 c
i (1 ≤ c
i ≤ n) &mdash ; 초기 행의 i번째 스톤의 색상.
출력:
단일 정수 인쇄 — 모든 보석을 제거하는 데 필요한 최소 시간(초).
예:
<몸>
| 입력 |
출력 |
3
1 2 1
| 1 |
3
1 2 3
| 3 |
7
1 4 4 2 3 2 1
| 2 |
설명:
세 번째 예의 시퀀스는 [1, 4, 4, 2, 3, 2, 1] -> [1, 4, 4, 1] -> []