How to solve this problem in O(log(n)*n) or less?

Revision en1, by pretending, 2021-07-17 14:22:43

I am stuck at this problem currently.

Problem Statement start

There are N stones numbered 1, 2,..., N. For each i (1<=i<=N), the height of the stone if hi. Here, h1<h2<...<hN holds.

There is a frog who is initially at Stone 1. He will repeat the following actions some number of times to reach stone N.

The frog that is currently Stone i can jump to one of the following stones — i+1, i+2,...,N such that a cost of (hj-hi)^2+C is incurred where j is the stone to land on.

Find the minimum possible total cost incurred before the frog reaches Stone N.

Input format

First line consists of 2 integers — N and C respectively. Second line consists of N integers.

Output format

Print the minimum possible total cost incurred before the frog reaches Stone N.

Problem Statement End

I have tried a O(n^2) approach but the accepted solution is supposedly O(log(n)*n) or less. How do solve this?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English pretending 2021-07-17 17:03:05 755
en1 English pretending 2021-07-17 14:22:43 1016 Initial revision (published)