比赛 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;
}