문제
'Blocks'라는 게임은 다음과 같다. 한 줄에 N개의 블록이 있고, 각 블록은 색을 가지고 있으며 아래 그림과 같다.
만약 인접한 블록들이 같은 색이 연속적으로 이어져 있으면, 같은 색깔로 이어진 맨 왼쪽의 박스부터 맨 오른쪽의 박스까지, 이러한 구간을 "블록 조각"이라고 한다.
위의 그림에서의 "블록 조각"들의 색은 다음과 같다. : 금, 은, 동, 금 각각 1개, 4개, 3개, 1개의 블록으로 조각들이 이뤄져있다.
박스를 클릭하게 되면 해당 블록이 위치한 블록 조각이 사라지게 되며, k개의 박스가 사라지게 되는데, 이 경우 k*k의 점수를 얻게 된다.
만약 위의 그림에서 은색으로 이뤄진 블록 조각을 클릭할 경우 4개의 블록이 사라지게 되며, 이 경우 4*4=16 점을 얻게 된다. 블록 조각이 사라지면, 블록 조각의 오른쪽에 있던 블록들이 왼쪽으로 이동하여 빈자리를 채우게 되며, 클릭하여 블록 조각을 제거하는 것을 반복하여 점수를 최대한 많이 얻는 것이 이 게임의 목적이다.
블록의 줄이 주어졌을 때 얻을 수 있는 최대 점수를 출력하는 프로그램을 작성하라. 위의 예시에 대해서는 아래의 두 번째 그림이 최적의 경우다.
입력
입력의 첫 번째 줄에는 블록의 개수 N(1<=N<=200)이 입력된다. 다음 줄에는 N개의 숫자가 들어오는데, 이는 블록에 붙은 색깔을 의미하는 숫자이다. 숫자의 범위는 1 이상 N 이하이며 같은 숫자가 붙을 경우 같은 색임을 뜻한다.
출력
얻을 수 있는 최고 점수를 한 줄에 출력한다.
예제
9
1 2 2 2 2 3 3 3 1
29
출처
POJ 1390
로그인해야 코드를 작성할 수 있어요.