考虑朴素做法：\(f_i\)表示通过桥架把第\(1\)根和第\(i\)根柱子连接的最小费用
，\(g_{i,j}\)表示用桥梁连接\(i\)和\(j\)的最小费用，\(s_i=\sum\limits_{j=1}^i{w_j}\)
考虑斜率优化\(DP\)：
考虑\(j_1<j_2,g_{i,j_2}<g_{i,j_1}\)的情况
此时应满足：
令\(y_i=f_i-s_i+{h_i}^2\)，化简得：
然而我们发现一个问题：\(h_{j_2}-h_{j_1}\)不一定大于\(0\)，但小于等于\(0\)又会导致两边不能同时除\(h_{j_2}-h_{j_1}\)，否则会导致不等式变号
考虑分治维护：
定义一个结构体\(a[i]\)，\(a[i].x=h_i,a[i].y=y_i,a[i].wz=i\)
因为对于\(i<j\)，\(f_j\)不会对\(f_i\)产生任何影响但\(f_i\)会对\(f_j\)产生影响。
那么对于区间\([l,r]\)，我们可以这么处理：
若\(l=r\)，则直接返回
若\(l<r\)，则令\(mid=(l+r)/2\)，将区间\([l,r]\)分成\([l,mid]\)和\([mid+1,r]\)递归先处理\([l,mid]\)的部分（不必管\([l,mid]\)怎么求，只要我们可以求出\([l,r]\)，又有边界条件，就可以求出\([l,mid]\)，毕竟是分治）。
将\(a[l,mid]\)和\(a[mid+1,r]\)排序，先按照\(a[i].x\)从小到大排，若\(a[i].x\)相同，则按\(a[i].y\)从小到大排（看上面那条式子，排序之后既保证了\((h_{j_2}-h_{j_1})\ge0\)又保证了\(h_i\)单调递增）
然后直接斜率优化\(DP\)用左边的\(f_j\)去更新右边的\(f_i\)，在递归处理\([mid+1,r]\)部分
细节再代码中体现，上代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e5+50;
ll n,f[N],w[N];
struct jgt
{
ll x,y,wz;
}a[N],b[N];
ll he,ta,q[N],s[N],h[N];
ll y(ll i){return f[i]-s[i]+h[i]*h[i];}
bool cmp(jgt t1,jgt t2)
{
return t1.x<t2.x;
}
void CDQ(ll l,ll r)
{
if(l==r)
{
a[l].y=y(l);
return ;
}
ll mid=(l+r)/2;
ll t1=l,t2=mid+1;
for(ll i=l;i<=r;i++)
if(a[i].wz<=mid) b[t1++]=a[i];
else b[t2++]=a[i];
for(ll i=l;i<=r;i++)
a[i]=b[i];
CDQ(l,mid);
he=1,ta=0;
for(ll i=l;i<=mid;i++)
{
if(i>l&&a[i].x==a[i-1].x) continue;
while(he<ta&&(a[i].y-a[q[ta]].y)*(a[q[ta]].x-a[q[ta-1]].x)<=(a[q[ta]].y-a[q[ta-1]].y)*(a[i].x-a[q[ta]].x)) ta--;
q[++ta]=i;
}
for(ll i=mid+1;i<=r;i++)
{
while(he<ta&&a[q[he+1]].y-a[q[he]].y<=2*a[i].x*(a[q[he+1]].x-a[q[he]].x)) he++;
ll u=a[i].wz,v=a[q[he]].wz;
f[u]=min(f[u],f[v]+s[u-1]-s[v]+(h[u]-h[v])*(h[u]-h[v]));
}
CDQ(mid+1,r);
t1=l,t2=mid+1;
ll t3=l;
while(t1<=mid&&t2<=r)
if(a[t1].x<a[t2].x||(a[t1].x==a[t2].x&&a[t1].y<a[t2].y)) b[t3]=a[t1],t1++,t3++;
else b[t3]=a[t2],t2++,t3++;
while(t1<=mid)
b[t3]=a[t1],t1++,t3++;
while(t2<=r)
b[t3]=a[t2],t2++,t3++;
for(ll i=l;i<=r;i++)
a[i]=b[i];
}
int main()
{
scanf("%lld",&n);
for(ll i=1;i<=n;i++)
{
scanf("%lld",&h[i]);
a[i].x=h[i];
}
for(ll i=1;i<=n;i++)
{
scanf("%lld",&w[i]);
a[i].wz=i;
s[i]=s[i-1]+w[i];
}
for(int i=2;i<=n;i++)
f[i]=1e16;
sort(a+1,a+n+1,cmp);
CDQ(1,n);
printf("%lld\n",f[n]);
return 0;
}