Naturalnym pomysłem na rozwiązanie zadania jest zastosowanie metody programowania dynamicznego. Będziemy wypełniać tabelkę, gdzie $d p [i]$ oznacza koszt budowy mostu kończącego się $i$ -tym filarem.

Dla uproszczenia najpierw zabezpieczymy pieniądze na wyburzenie wszystkich filarów w wysokości $W = \sum_{i} w_{i}$ . Dzięki temu będziemy mogli uwzględniać koszt niewyburzenia filaru równy $- w_{i}$ .

Zatem $d p [1] = - w_{1}$ , bo mamy wtedy most składający się z pierwszego filaru. Dla $i > 1$ mamy prostą zależność rekurencyjną: $d p [i] = min_{j < i} (d p [j] + (h_{i} - h_{j})^{2} - w_{i}) .$

Odpowiedzią jest oczywiście $d p [n] + W$ , a całość można zapisać następującym programem działającym w czasie $O (n^{2})$ :

const int N = 110000;
int n,h[N],w[N];
ll dp[N],sumw;

ll sq(int x) { return ll(x)*x; }

int main() {
  scanf("%d",&n);
  REP(i,n) scanf("%d",&h[i]);
  REP(i,n) scanf("%d",&w[i]);

  REP(i,n) sumw += w[i];

  dp[0] = -w[0];
  for (int i=1; i<n; ++i) {
    dp[i] = ll(1e18);
    for (int j=i-1; j>=0; --j) {
      dp[i] = min(dp[i], dp[j] + sq(h[i] - h[j]) - w[i]);
    }
  }

  ll ans = dp[n-1] + sumw;
  printf("%lld\n", ans);
}

Rozwiązanie wzorcowe

Możemy trochę inaczej rozpisać sobie koszt budowy. Przęsło mostu między filarami $i$ oraz $j$ kosztuje $(h_{i} - h_{j})^{2} = h_{i}^{2} - 2 h_{i} h_{j} + h_{j}^{2} .$ Składniki $h_{i}^{2}$ będą występować w sumarycznym koszcie dwukrotnie dla każdego wybranego filaru (oprócz pierwszego i ostatniego, dla których będą występować jednokrotnie). Zatem możemy zmienić koszt budowy przęsła na $2 h_{i}^{2} - 2 h_{i} h_{j},$ a następnie całkowity koszt to będzie $W - w_{1} + h_{1}^{2} - h_{n}^{2}$ plus koszt wynikający z budowy przęseł.

Niech $d p [i]$ będzie kosztem budowy mostu kończącego się $i$ -tym filarem. Wtedy $d p [i] = min_{j < i} (d p [j] - w_{i} + 2 h_{i}^{2} - 2 h_{i} h_{j}) = min_{j < i} (a_{j} (- 2 h_{i}) + b_{j} + c_{i}),$ gdzie $a_{j} = d p [j]$ oraz $b_{j}$ są pewnymi stałymi dla $j$ -tego filaru, a $c_{i} = - w_{i} + 2 h_{i}$ jest stałą dla $i$ -tego filaru.

Tak więc potrzebujemy umieć minimalizować wartości funkcji liniowych $a_{j} x + b_{j}$ dla zbioru filarów, oraz dodać taką funkcję $a_{i} x + b_{i}$ dla nowego filaru.

Poniżej kod, który nieefektywnie realizuje taką strukturę w czasie $O (n^{2})$ :

struct oracle {
  vector<pair<ll,ll>> v;

  ll get(ll x) {
    ll ans = 1e18;
    for (auto [a, b] : v) {
      ans = min(ans, a*x + b);
    }
    return ans;
  }

  void insert(ll a, ll b) {
    v.emplace_back(a, b);
  }
};

int main() {
  scanf("%d",&n);
  REP(i,n) scanf("%d",&h[i]);
  REP(i,n) scanf("%d",&w[i]);

  REP(i,n) sumw += w[i];

  oracle s;
  s.insert(h[0], sumw - w[0] + sq(h[0]) - sq(h[n-1]));
  for (int i=1; i<n; ++i) {
    cost = -w[i] + 2*sq(h[i]) + s.get(-2*h[i]);
    s.insert(h[i], cost);
  }

  printf("%lld\n", cost);
}

Ale strukturę danych można zaimplementować, aby operacje działały w zamortyzowanym czasie $O (\log n)$ . Jest to tzw. convex hull optimization, gdzie utrzymujemy górną otoczkę wypukłą zbioru równań liniowych. Poniżej przykładowa implementacja tego pomysłu:

const ll infty = 1e18;

inline ll ceil_div(ll a, ll b) {
  assert(b > 0);
  if (a < 0) return -( (-a)/b );
  else return (a + b-1) / b;
}

struct line {
  ll a, b;
  mutable ll xl;

  bool operator<(const line& other) const {
    if (max(a, other.a) == infty+1) {
      return xl < other.xl;
    } else {
      return make_pair(a, b) < make_pair(other.a, other.b);
    }
  }

  ll inters(const line& prev) const {
    return ceil_div(prev.b - b, a - prev.a);
  }

  bool valid(const line& prev, const line& next) const {
    return inters(prev) < next.inters(*this);
  }

  void update(const line& prev) const {
    xl = inters(prev);
  }
};

struct envelope {
  set<line> s;

  void insert(ll a, ll b) {
    assert(max(abs(a), abs(b)) <= infty);

    auto it = s.insert({ a, b, -2*infty }).first;

    if (next(it) != s.end() && a == next(it)->a) {
      s.erase(it);
      return;
    }
    if (it != s.begin() && prev(it)->a == a) {
      s.erase(prev(it));
    }

    if (it != s.begin() && next(it) != s.end() && !it->valid(*prev(it), *next(it))) {
      s.erase(it);
      return;
    }

    if (it != s.begin()) {
      auto pit = prev(it);
      while (pit != s.begin() && !pit->valid(*prev(pit), *it)) {
        s.erase(pit);
        pit = prev(it);
      }
      it->update(*pit);
    }

    if (next(it) != s.end()) {
      auto nit = next(it);
      while (next(nit) != s.end() && !nit->valid(*it, *next(nit))) {
        s.erase(nit);
        nit = next(it);
      }
      nit->update(*it);
    }
  }

  bool empty() const { return s.empty(); }
  void clear() { s.clear(); }

  pair<ll,ll> eval(ll x) const {
    auto it = prev(s.upper_bound({ infty+1, 0, x }));
    return make_pair(it->a, it->b);
  }
};

struct oracle {
  envelope env;

  ll get(ll x) {
    auto [a, b] = env.eval(x);
    return -a*x - b;
  }

  void insert(ll a, ll b) {
    env.insert(-a, -b);
  }
};