4490: 「CEOI2017」Building Bridges
内存限制：128 MB
时间限制：3.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
有 $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$。
输出
输出一行一个整数表示最小代价，注意最小代价不一定是正数。
样例输入 复制
6
3 8 7 1 6 6
0 -1 9 1 2 0样例输出 复制
17提示
数据范围：对于 $100\%$ 的数据，有 $2\le n\le 10^5;0\le h_i,\vert w_i\vert\le 10^6$。 * 子任务 1（$30\%$）：有 $n\le 1000$； * 子任务 2（$30\%$）：有 $\vert w_i\vert \le 20$，保证存在一种最优方案，除了头尾两根柱子外，最多只保留两根柱子； * 子任务 3（$40\%$）：无特殊限制。