Seems too easy, maybe you missed some constraint. For sure we can say that lower bound on DP[N] is X[N]-X[1] because of the cost function. Now we have two cases, let Ym = max(Y1, Y2, .., YN): Ym <= X[N]-X[1] -> then we can achieve the lower bound by saying DP[N] = DP[0] + cost(1, N) = X[N]-X[1]. Ym > X[N]-X[1] -> now that also means Ym > X[j]-X[i], for every i,j pair. So at least one of the cost functions on our path from 0 to N will be equal to Ym. That means lower bound on DP[N] is Ym. But again we can achieve that by DP[N] = DP[0] + cost(1, N) = Ym.

Seems that I could solve it in O(n log^2 n). Main idea that problem for Cost(s, e) = X[e] — X[s], could be solved easily by keeping DP[j]-X[j+1], for Cost(s, e) = Max(Y[s], Y[s+1] ... Y[e]) by segment tree with maximum on DP[j]+Max(Y[j+1], ... Y[i]) and multi-addition operation (when maximums on current suffixes of Y increases you should add difference on suffix of suffixes. Invariant is that if two maximums became same they became same forever and all future adds could be done as multi-adds). So we need separate cases where X[e] — X[s] < Max(Y[s], Y[s+1] ... Y[e]. It could be done by two-dimentional segment tree in the similar manner as described above for case Cost(s, e) = Max(Y[s], Y[s+1] ... Y[e]).

Disclaimer that it's 4am here, so my idea may make sense or not:

Let's write max(Y_j, Y_j + 1, ..., Y_i) = Y(j, i). When we are processing i, for every j we want to know if Y(j, i) >  = X_i - X_j, or Y(j, i) - X_j ≥ X_i. So we can use two trees: one stores min value of dp[j] + X_j - X_i for every interval of Y(j, i) - X_j, the other one stores min value of dp[j] + Y(j, i) for every interval of Y(j, i) - X_j, and then finding the optimal value of dp[j] can be reduced to simply querying both trees (you can do it in a single tree of course, but I'm saying two for simplicity).

Of course, Y(j, i) can change when we change i. We can fix this by updating our trees, removing j from both trees, calculating the new value of Y(j, i) - X_j, and adding it again. But wait, every Y(j, i) can change n times, so this is even worse than if you simply do the loop.

So let's exploit one property of Y(j, i) mentioned by zeliboba -- namely that once two maximums become equal they become equal forever. Every time Y(j, i) changes, group of k with Y(k, i) = Y(j, i) necessarily increases size. If this group becomes larger than , let's create separate trees specifically for this group, remove all j inside group from the global trees and add all j in group to these group trees.

Now we have interesting property: whenever Y(j, i) changes for one element in the group, it changes for all other elements of the group, so the order in the group tree remains the same. That means that group tree will never need to be updated again (unless a new j enters the group, in which case it should be added to the group tree). Whenever you're querying for the best j for a certain i, you now need to check the generic tree and all group trees for the optimal value.

Complexity analysis: Because each change increases group size, each element j changes Y(j, i) at most times before it enters a group of more than elements. When querying for the minimum value, we will need to query at most trees (general trees and group trees). So we can see both queries and updates are bound by .