BOJ 6101 - 식당
항상 정답은 이하이다. 모두 길이 의 그룹으로 묶으면 되기 때문이다.
정답이 줄어드는 경우는 서로다른 개의 수를 가진 집합이라면 길이가 최소 초과여야 한다.
이는 인 가지의 경우만 각각 따지면 된다는 것을 의미한다.
를 로 끝나는 서로 다른개의 숫자가 나오는 구간의 가장 왼쪽이라고 하자.
에 투포인터로 전처리가 가능하다.
그럼 이제 $dp[i]=\text{Min}{j=1}^{\sqrt{ i }} dp[L{i,j}-1]+j^2$ 임을 알 수 있고 문제를 해결가능하다.
Comments