比赛场次 652
比赛名称 赤石大赛
比赛状态 已结束比赛成绩
开始时间 2024-12-20 14:00:00
结束时间 2024-12-20 18:00:00
开放分组 全部用户
注释介绍 赤石大赛(1绿3紫2黑)快来赤石
题目名称 Building Bridges
输入输出 jiaqiao.in/out
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分

Building Bridges

★★★☆   输入文件:jiaqiao.in   输出文件:jiaqiao.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目描述】

有 $n$ 根柱子依次排列,每根柱子都有一个高度。第 $i$ 根柱子的高度为 $h_i$。


现在想要建造若干座桥,如果一座桥架在第 $i$ 根柱子和第 $j$ 根柱子之间,那么需要 $(h_i-h_j)^2$ 的代价。


在造桥前,所有用不到的柱子都会被拆除,因为他们会干扰造桥进程。第 $i$ 根柱子被拆除的代价为 $w_i$,注意 $w_i$ 不一定非负,因为可能政府希望拆除某些柱子。


现在政府想要知道,通过桥梁把第 $1$ 根柱子和第 $n$ 根柱子连接的最小代价。注意桥梁不能在端点以外的任何地方相交。

【输入格式】

第一行一个正整数 $n$。

第二行 $n$ 个空格隔开的整数,依次表示 $h_1,h_2,\cdots,h_n$。

第三行 $n$ 个空格隔开的整数,依次表示 $w_1,w_2,\cdots,w_n$。

【输出格式】

输出一行一个整数表示最小代价,注意最小代价不一定是正数。

【样例1输入】

6
3 8 7 1 6 6
0 -1 9 1 2 0

【样例1输出】

17

【样例2/3/4】

点击下载样例2/3/4 

【数据规模与约定】

对于 $20\%$ 的数据,$n \le 1000$;

对于 $30\%$ 的数据,$\vert w_i \vert \le 20$,保证存在一种最优方案,除了头尾两根柱子外,最多只保留两根柱子;

对于 $50\%$ 的数据,无特殊限制。

对于 $100\%$ 的数据,有 $2 \le n \le 10^5;0 \le h_i,\vert w_i \vert \le 10^6$。