DP Optimization Challenge from Korean OI

Revision en1, by ko_osaga, 2016-03-11 08:18:19

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?

Tags dp, optimization, koi

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English ko_osaga 2016-03-11 08:18:19 707 Initial revision (published)