比赛 |
2022级DP专题练习赛7 |
评测结果 |
AAAAAAAAAA |
题目名称 |
Building Bridges |
最终得分 |
100 |
用户昵称 |
yrtiop |
运行时间 |
0.838 s |
代码语言 |
C++ |
内存使用 |
7.64 MiB |
提交时间 |
2023-02-27 19:40:03 |
显示代码纯文本
#include <bits/stdc++.h>
using i64 = long long;
using ld = long double;
const int maxn = 1e5 + 5;
const ld eps = 1e-10;
const ld INF = 1e16;
int n,idx[maxn],stk[maxn],tp;
i64 h[maxn],w[maxn],s[maxn],f[maxn];
i64 calcy(int x) {
return f[x] - s[x] + h[x] * h[x];
}
i64 calcx(int x) {
return 2ll * h[x];
}
ld slope(int i,int j) {
ld dy = calcy(j) - calcy(i),dx = calcx(j) - calcx(i);
if(std::fabs(dx) < eps)
return (dy < 0) ? INF : -INF;
return dy / dx;
}
void solve(int l,int r) {
if(l >= r)
return ;
int mid = (l + r) >> 1;
solve(l , mid);
for(int i = l;i <= mid;++ i)
idx[i] = i;
std::sort(idx + l , idx + mid + 1 , [&](const int& x,const int& y) {
return h[x] < h[y];
});
stk[tp = 0] = 0;
for(int i = l;i <= mid;++ i) {
while(tp > 1&&slope(stk[tp] , stk[tp - 1]) >= slope(idx[i] , stk[tp]))
stk[tp --] = 0;
stk[++ tp] = idx[i];
}
for(int i = mid + 1;i <= r;++ i) {
int L = 1,R = tp - 1,M;
while(L <= R) {
M = (L + R) >> 1;
if(slope(stk[M + 1] , stk[M]) <= (ld)h[i])
L = M + 1;
else
R = M - 1;
}
f[i] = std::min(f[i] , f[stk[L]] + s[i - 1] - s[stk[L]] + 1ll * (h[i] - h[stk[L]]) * (h[i] - h[stk[L]]));
}
solve(mid + 1 , r);
return ;
}
int main() {
freopen("jiaqiao.in","r",stdin);
freopen("jiaqiao.out","w",stdout);
scanf("%d",&n);
for(int i = 1;i <= n;++ i)
scanf("%lld",&h[i]);
for(int i = 1;i <= n;++ i)
scanf("%lld",&w[i]),s[i] = s[i - 1] + w[i];
for(int i = 1;i <= n;++ i)
f[i] = 1e16;
f[1] = 0;
solve(1 , n);
printf("%lld\n",f[n]);
return 0;
}