문제
최근에 슬아는 유행하는 블록퍼즐을 즐기고 있다.
블록 퍼즐의 규칙은 다음과 같다. N개의 블록이 존재하고, 블록의 색깔은 M가지다.
편의상 블록의 색깔은 1부터 M의 정수로 표현한다.
N개의 블록은 한 줄로 늘어져 있으며, 한 번에 앞의 블록부터 하나씩 혹은, 연달아 없앨 수 있다.
블록을 없앨 경우 얻게 되는 점수는 K x K 인데, 여기서 K는 한 번에 없애고자 하는 블록들의 색깔의 종류수를 뜻한다.
만약에 한 번에 없애고자 하는 블록이 [ 3 4 3 4 3 ] 이면 색의 종류가 2개 이므로 이때 받게 되는 점수는 2 x 2 = 4 다.
블록을 전부 없앴을 때 얻게 되는 점수가 최소가 되게 하는 것이 이 게임의 목표다.
슬아는 이 퍼즐을 풀다가 가능한 최소의 점수가 몇 점인지 알아볼 수 있지 않을까 생각하였고, 친구인 당신과 함께 풀어보고자 한다.
아래 등장하는 예시의 경우에는 다음과 같이 블록을 없애면 된다.
[ ] 안에 있는 블록들은 한 번에 없애게 되는 블록이며, 이 경우 얻게 되는 점수는 11이다.
[ 1 ] [ 2 ] [ 1 ] [ 3 ] [ 2 2 ] [ 3 4 3 4 3 ] [ 1 ] [ 4 ]
입력
입력의 첫 번째 줄에는 블록의 개수 N(1≤N≤40,000) 종류 M(1≤M≤N)이 입력된다. 그 다음 줄부터 N개의 줄에는 블록의 종류가 순서대로 입력된다. 각 블록의 색상은 1번부터 M번 이하의 정수로 입력된다.
출력
입력에 대해서 모든 블록을 없앨 경우에 최소 점수를 출력한다.
예제
13 4
1
2
1
3
2
2
3
4
3
4
3
1
4
11
출처
USACO MAR09 Gold Cleaning Up (Paul Christiano, 2007)
로그인해야 코드를 작성할 수 있어요.