比赛 NOIP2025模拟赛2 评测结果 AAAAAEEEEEEEEEEE
题目名称 桥梁建设 最终得分 31
用户昵称 徐诗畅 运行时间 1.667 s
代码语言 C++ 内存使用 3.51 MiB
提交时间 2025-11-25 11:38:51
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1005;
int n,h[N],w[N],f[N];
signed main(){
	freopen("building.in","r",stdin);
	freopen("building.out","w",stdout); 
	scanf("%lld",&n);
	for(int i = 2;i<=n;i++) f[i]=1e15;
	for(int i = 1;i<=n;i++) scanf("%lld",&h[i]);
	for(int i = 1;i<=n;i++) scanf("%lld",&w[i]),w[i]+=w[i-1];
	for(int i = 2;i<=n;i++){
		for(int j = 1;j<i;j++)
		f[i]=min(f[i],f[j]+(h[i]-h[j])*(h[i]-h[j])+w[i-1]-w[j]);
	}
	printf("%lld",f[n]);
	return 0;
}