比赛 NOIP2025模拟赛2 评测结果 TTTTTTTTTTTTTTTT
题目名称 桥梁建设 最终得分 0
用户昵称 123 运行时间 33.607 s
代码语言 C++ 内存使用 3.27 MiB
提交时间 2025-11-25 12:17:58
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,x,y,h[N],w[N],mp[N];
long long dp[N],a[N],ret=1e18;
inline void read(int &x)
{
    int k=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
	x=k*f; 
}
int main() {
	freopen("building.in","r",stdin); 
	freopen("building.out","w",stdin); 
	read(n);
	for (register int i=1;i<=n;i++) read(h[i]);
	for (register int i=1;i<=n;i++) read(w[i]),a[i]=a[i-1]+w[i]; 
	memset(dp,0x3f,sizeof(dp));
	dp[1]=0;
	for (register int i=2;i<=n;i++)
	{
//		cout<<dp[i]<<endl; 
		for (register int j=1;j<i;j++)
		{
			dp[i]=min(dp[j]+a[i-1]-a[j]+1ll*(h[i]-h[j])*(h[i]-h[j]),dp[i]);
		}
	}
	cout<<dp[n];
}