I am referring to ->https://codeforces.net/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

I am referring to problem- https://codeforces.net/problemset/problem/1067/A. I did refer to the editorial for this problem and well, it is really hard to understand. I do get the overall sketch of the solution but there are a few ambiguities in the language of the editorial- https://codeforces.net/blog/entry/62688. I still got no idea what "flag" state is doing in dp. Perhaps the editorial writer wanted to say(i am using the same notation as used in the editorial) "flag=0 when the a[prefix-1]<=a[prefix] " or something like that. Can anyone help me figure out what exactly the editorial wants to say? I will be really thankful. I know it is kinda ..............frustrating to go through a problem statement and then the editorial to try and understand what I am trying to ask. But both the problem statement and editorial for the problem won't take too long to read. Thank you