小清新斜率优化题。
分段问题显然 dp，令 \(f_i\) 为将第 \(1\) 根柱子和第 \(i\) 根柱子连接的最小代价。\(f_1=0\)，每次枚举 \(i\) 向前直接连接的柱子：
\[f_{i}=\min\limits_{j=1}^{i-1}\left\{f_j+(h_i-h_j)^2+\sum\limits_{k=j+1}^{i-1}w_k\right\}
\]
令 \(s_{i}=\sum\limits_{j=1}^iw_j\)，然后把转移拆开，假设最优决策点为 \(j\)：
\[f_i=f_j+(h_i-h_j)^2+s_{i-1}-s_{j}
\]
\[f_i=f_j+h_i^2+h_j^2-2h_jh_i+s_{i-1}-s_{j}
\]
\[f_{i}-s_{i-1}-h_i^2=f_j-s_j+h_j^2-2h_j\times h_i
\]
平凡的斜率优化会把上式写成 \(b=y-xk\) 的形式，但我们旋转一下坐标系，令 \(y_i=f_{i}-s_{i-1}-h_{i}^2\)，\(b_j=f_j-s_j+h_j^2\)，\(k_j=-2h_j\)，\(x_i=h_i\)：
\[y_i=k_jx_i+b_j
\]
于是我们得到了斜率优化的另一种形式。
我们可以将转移点 \(j\) 看作平面上的一条条形如 \(y=k_jx+b_j\) 的直线，每次即查询一个 \(x\) 坐标上 \(y\) 坐标最小的值，支持动态插入一条直线。
李超线段树维护即可。复杂度 \(O(n\log w)\)。
#include <bits/stdc++.h>
#define int long long
using namespace std;
namespace vbzIO {
char ibuf[(1 << 20) + 1], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
#define pi pair<int, int>
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define ins insert
#define era erase
inline int read () {
char ch = gh();
int x = 0;
bool t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
return t ? ~(x - 1) : x;
}
inline void write(int x) {
if (x < 0) {
x = ~(x - 1);
putchar('-');
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
}
using vbzIO::read;
using vbzIO::write;
const int maxn = 1e5 + 100;
const int maxw = 1e6 + 100;
const int inf = 1e18;
int n, h[maxn], w[maxn], s[maxn], f[maxn], tr[maxw << 2];
#define ls x << 1
#define rs x << 1 | 1
#define mid ((l + r) >> 1)
int K(int id) { return - 2 * h[id]; }
int B(int id) { return id ? (f[id] - s[id] + h[id] * h[id]) : inf; }
int gety(int id, int x) { return K(id) * x + B(id); }
int cmp(int x, int y) { return x == y ? 0 : (x > y ? 1 : -1); }
void push(int l, int r, int s, int x) {
int &t = tr[x];
if (cmp(gety(s, mid), gety(t, mid)) == -1) swap(s, t);
int fl = cmp(gety(s, l), gety(t, l)), fr = cmp(gety(s, r), gety(t, r));
if (fl == -1 || (!fl && s < t)) push(l, mid, s, ls);
if (fr == -1 || (!fr && s < t)) push(mid + 1, r, s, rs);
}
int qry(int l, int r, int p, int x) {
if (l == r) return gety(tr[x], p);
int res = gety(tr[x], p);
if (p <= mid) return min(res, qry(l, mid, p, ls));
else return min(res, qry(mid + 1, r, p, rs));
}
signed main() {
n = read();
for (int i = 1; i <= n; i++) h[i] = read();
for (int i = 1; i <= n; i++) w[i] = read(), s[i] = s[i - 1] + w[i];
push(0, 1e6, 1, 1);
for (int i = 2; i <= n; i++) {
int j = qry(0, 1e6, h[i], 1);
f[i] = j + s[i - 1] + h[i] * h[i];
push(0, 1e6, i, 1);
}
write(f[n]);
return 0;
}