Let's first slightly change the problem to focus only on the pillars that support the bridge and not the other ones which should be destroyed. The overall cost consists of the cost due to differences in heights plus the cost of destroying unused pillars. The latter one is equal to the sum of all destruction cost minus the cost of those that are retained.

Dynamic programming. Consider a subproblem of building the bridges such that the last one ends on pillar ~i~. Let ~f(i)~ represent the minimum cost of solving this subproblem. The last bridge in the solution will span from some pillar ~j < i~ to ~i~, which results in the formula:

$$\displaystyle \begin{align*} f(1) &= -w_1 \\ f(i) &= \min_{j<i} \left(f(j) + (h_j-h_i)^2 - w_i\right) \end{align*}$$

A dynamic programming solution has to solve ~\mathcal O(n)~ subproblems, spending ~\mathcal O(n)~ time on each.

Two pillars. Can we do better if we know that the optimal solution consists only of two additional pillars besides the first and the last? If there's only one additional pillar, we can simply try them all. For the case of two additional pillars, we'll try all second pillars ~i~ and for each of them choose an optimal first pillar ~j~.

The contribution of the first pillar to the overall cost is ~(h_1-h_j)^2 + (h_j-h_i)^2 - w_j~. Let's ignore ~w_j~ for now (assume ~w_j = 0~). Intuitively, we would want to choose ~h_j~ close to the average of ~h_1~ and ~h_i~. Calculating where derivative equals zero confirms our intuition. Therefore, we are interested in only two pillars — the largest among those smaller or equal to ~(h_1+h_i)/2~ and the smallest among those larger. As we try different pillars ~i~ from ~1~ to ~n~, we can maintain a tree structure of pillars ~j < i~ ordered by their height. This allows us to find the two we need in ~\mathcal O(\log n)~. For example, we can use the set data structure from C++ for this purpose.

All that's left is to handle the term ~w_j~. Their limited range of values is helpful in this case. We can maintain separate tree structures for every value of ~w_j~ and look for the optimal pillar ~j~ for every possible value of ~w_j~. The time complexity is ~\mathcal O(na \log n)~, ~a = \max |w_i|~.

Convex optimization. Let's rewrite the recursive definition from the dynamic programming solution.

$$\displaystyle \begin{align*} f(i) &= \min_{j<i} (A(j) \times h_i + B(j) + C(i)) \\ A(j) &= -2hj \\ B(j) &= h_j^2 + f(j) \\ C(i) &= h_i^2 - w_i \end{align*}$$

Note that ~C~ is a constant term that depends only on ~i~ and is the same regardless of the choice of ~j~. If the term ~A(j) \times h_i~ weren't present, we could simply maintain the best choice of ~j~ as we compute values of ~f(i)~ for increasing ~i~. Term ~h_i~ in the product complicates things. We can consider every pair ~A(j)~ and ~B(j)~ as a slope and ~y~-intercept of a line. The problem of finding the best ~j~ reduces to finding the lowest line at ~x = h_i~. To do this in ~\mathcal O(\log n)~, we'll maintain a lower envelope of a set of lines. The data structure has to be dynamic — it should support insertion of a new line in ~\mathcal O(\log n)~. Note that the lines comprising the lower envelope are ordered by their slope. Therefore, we can maintain a tree structure of these line segments. It allows us to quickly find the optimal line for a given ~x~ as well as insert a new one. We can abuse C++'s set for this purpose. This optimization is often called the convex hull trick in relation to dynamic programming and solves the problem in ~\mathcal O(n \log n)~ time.