Help in a Dp problem

Revision en1, by practicener, 2020-10-29 18:07:38

I am referring to ->https://mirror.codeforces.com/contest/1012/problem/C I could come up with O(n^3) solution-> Let dp[i][j]= minimum cost to build j houses in the first i hills. We iterate over the continuous segments, at the end points of which , we build the houses. That is -> if we are considering a segment 1...........i we can break it as 1......k-1 [ k..........i] However this will not fit in the constraints. The editorial is a bit too hard to understand. Can someone please suggest some way to reduce the complexity to O(n^2) . Thank you

Tags dp, div1

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English practicener 2020-10-29 18:07:38 573 Initial revision (published)