I got a nice problem from Korean OI : https://www.acmicpc.net/problem/2300 .

Since deriving recurrence is not the point of this topic, I will give you the formula :

• N <= 10000

• 0 <= Xi <= X(i+1) <= 10^9, (1 <= i < N), 0 <= Yi <= 10^9 (1 <= i <= N)

• DP[i] = Min(DP[j] + Cost(j+1, i))for all j < i. when Cost(s, e) = Max(X[e] — X[s], Max(Y[s], Y[s+1] ... Y[e]))

The goal is to calculate DP[N] — and O(N^2) solution is quite straightforward.

However, I heard that there is a subquardatic solution to this problem! I tried various strategies to solve it, but failed.

Does anyone have a hint / idea to the subquadratic solution?