The Small Castle Built by a Dwarf

$i$번째 성까지 처리했고 마지막 높이가 $h$일 때의 최소 비용을 $F_i(h)$라 하자. 전이는

$$F_i(h)=\mathrm{cost}_i(h)+\min(F_{i-1}(h-1),F_{i-1}(h+1))$$

이다.

높이의 홀짝을 나누고 $h=2x+p$로 두면 각 홀짝에서 $F_i$는 이산 볼록함수이다. 인접한 두 상태 중 최솟값을 취하는 연산은 볼록함수에 대한 길이 $1$ 구간 최소화로 바뀐다. 이는 slope trick의 왼쪽과 오른쪽 지연값을 각각 옮겨 처리할 수 있다.

높이 변경 비용도 볼록함수이다. $H_i-p$가 짝수이면 같은 꼭짓점을 갖는 두 비대칭 V자 함수를 더하고, 홀수이면 서로 이웃한 두 꼭짓점에 하나씩 더하면 $h=2x+p$에서의 비용과 정확히 일치한다. 양의 높이 조건은 가능한 모든 실제 비용 기울기의 합보다 큰 가중치로 $x$의 하한을 강제한다.

가중치가 있는 두 우선순위 큐로 slope trick을 구현하면 각 꼭짓점이 로그 시간에 처리된다. 전체 시간 복잡도는 $O(N\log N)$이다. 비용 계산에는 128비트 정수를 사용한다.