题解

思路概述

• 留下的柱子将按照高度递增的顺序连成一条折线。若我们选择了柱子 $j<i$ 与柱子 $i$ 之间架桥，那么桥的代价为 $(h_i-h_j)^2$，并且在区间 $(j,i)$ 内的所有柱子都要拆除，其总代价为 $w_{j+1}+w_{j+2}+\dots+w_{i-1}$。于是最优策略可以写成 DP：
  设 dp[i] 表示最终保留第 $i$ 根柱子的最小代价，则$$dp[i]=\min_{1\le j<i}\{dp[j]+(h_i-h_j)^2+\sum_{k=j+1}^{i-1}w_k\}. $$
• 对式子做前缀和变形，令 s[i] = Σ_{k=1}^{i} w_k，则$$dp[i]=h_i^2+s[i-1]+\min_{j<i}\{\underbrace{dp[j]-s[j]+h_j^2}_{y_j}-2h_i h_j\}. $$这显然是把每个历史状态视为一条形如 $f_j(x)=k_j x+b_j$ 的直线（其中 $x= h_i$，$k_j=-2h_j`，`b_j=y_j`），对当前的$h_i$ 查询最小值。
• 由于高度没有单调性，不能直接用凸包，但可以按照下标做分治：在 CDQ 分治的“左半段”维护所有候选转移，按照斜率排序加入凸壳；“右半段”依次按 $h_i$ 查询即可。整套流程与传统的 CDQ + 斜率优化一致。

实现细节

• Sort(l,r) 负责分治。对中点左侧的所有下标 $id[i]`$ 按照 $h$ 排序，用单调栈维护下凸壳；右半侧按 $h_i$ 二分凸壳求最优转移并更新 dp。
• 注意到同一高度可能重复，代码中特判了坐标相等时的处理，保证凸壳满足斜率严格递增，从而查询时二分有效。
• 最终答案就是 dp[n]；初始化时让 dp[1] = 0，其余位置赋予正无穷。

复杂度

每一层分治会把所有点恰好加入一次凸壳、查询一次，故时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1e5 + 10;

struct Node {
    ll x, y;
    bool operator < (const Node &i) const {
        return x * i.y < y * i.x;
    }
    bool operator == (const Node &i) const {
        return x * i.y == y * i.x;
    }
};

int n, a[N], stk[N], top, tmp[N], id[N];
ll s[N], dp[N], y[N], x[N];

Node P(int i, int j) {
    return {y[j] - y[i], x[j] - x[i]};
}

void Sort(int l, int r) {
    if (l == r) return ;
    int mid = (l + r) >> 1;
    Sort(l, mid);
    for (int i = l; i <= mid; i++) {
        y[id[i]] = dp[id[i]] - s[id[i]] + 1ll * a[id[i]] * a[id[i]];
        while (top >= 2 && (x[id[i]] == x[stk[top]] ? y[id[i]] <= y[stk[top]] : P(stk[top], id[i]) < P(stk[top - 1], stk[top]))) top--;
        stk[++top] = id[i];
    }
    for (int i = mid + 1; i <= r; i++) {
        int ql = 2, qr = top + 1;
        while (ql < qr) {
            int mid = (ql + qr) >> 1;
            P(stk[mid - 1], stk[mid]) < Node{a[id[i]], 1} ? ql = mid + 1 : qr = mid;
        }
        dp[id[i]] = min(dp[id[i]], y[stk[ql - 1]] - 2ll * a[id[i]] * a[stk[ql - 1]] + 1ll * a[id[i]] * a[id[i]] + s[id[i] - 1]);
    }
    fill(stk + 1, stk + top + 1, 0), top = 0, Sort(mid + 1, r);
    for (int i = l, j = mid + 1, k = l; i <= mid || j <= r; k++) {
        if (j > r || (i <= mid && x[id[i]] < x[id[j]]) || (i <= mid && x[id[i]] == x[id[j]] && y[id[i]] < y[id[j]])) tmp[k] = id[i++];
        else tmp[k] = id[j++];
    }
    for (int i = l; i <= r; i++) id[i] = tmp[i];
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], x[i] = 2 * a[i], id[i] = i;
    for (int i = 1, k; i <= n; i++) cin >> k, s[i] = s[i - 1] + k;
    fill(y + 1, y + n + 1, 1e18);
    // dp[i] = min(dp[j] - s[j] + h[j] ^ 2 - 2 * h[i] * h[j]) + s[i - 1] + h[i] ^ 2
    // k = h[i], x = 2 * h[j], y = dp[j] - s[j] + h[j] ^ 2
    fill(dp + 2, dp + n + 1, 1e18), Sort(1, n);
    cout << dp[n];
    return 0;
}