Skip to content

11091: 【原1091】"不吃米"芯片

题目

题目描述

author: duruofei 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1091

Description

流光复刻,记忆成诗,人的大脑里发生的一切是瞬息万变,甚至的不可预知的,然而,正是有了神奇的大脑,我们才有了自我意识。

如果用PN结、MOS、BJT、调谐放大器制成的机器人也能进化,能有意识的行动,那么是否有一天,机器人也会变得和人一样有意识?

电脑的硬件也许能像自然界人类和其他生物进化的方式进行进化这一想法,早在上世纪60年代就被提出。

这一灵感就是被称为BCMI芯片的高集成度可编程集成电路块,简称为"不吃米"芯片。

好好看题的孩子会有奖励:w[i][j]自己算一下,100分四边形不等式哦亲~80也不少了 ~

最近,BCMI的小M发现,对BCMI芯片的关键逻辑元进行重组后产生一种奇特的现象。

将若干关键逻辑元按照电路板平面坐标系2维降序排列,经过机器学习、模式识别、神经网络、数理逻辑(乱入)、数据挖掘……

这些关键逻辑元自动按照x坐标和y坐标方向联接成一棵树。

这棵树的每条边都平行于x坐标轴或平行于y坐标轴。

关键逻辑元构成这棵树的全部叶结点。

这类树称为以关键逻辑元为叶结点的正交树。

有趣的是,BCMI芯片自动产生的正交树的总边长是所有这种正交树中总边长最小的!

例如,将5个关键逻辑元分别置于电路板xoy坐标系中(1,5),(2,4),(3,3),(4,2)和(5,1)处,

则BCMI芯片自动产生的一棵正交树如下图所示,它的总边长为12。

Input Format

第1行中的整数为关键逻辑元个数n;

接下来的n行中每行一个整数,依次为 X1, X2, X3, ..., Xn;(升序排列)

最后的n行中每行一个整数,依次为 Y1, Y2, Y3, ... ,Yn。(降序排列)

Output Format

输出一行一个整数,表示所找到的最优正交树总边长的值~

Hint

对于40分的数据 n < 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089

对于70分的数据 n < 301

对于80分的数据 n < 600

对于100分的数据 n < 3001

标程保证所有数不超过int的范围

Sample Input1

5
1
2
3
4
5
5
4
3
2
1

Sample Output1

12

Sample Input2

5
1547
2424
6657
6803
9536
8397
8161
7421
1261
882

Sample Output2

21733

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!