P1010 阿凡达计划

P1010 阿凡达计划

题目背景
潘多拉星球上有一种特别的矿物元素“unobtanium”,它将彻底改变人类的能源产业,正是受此吸引地球人才不远万里来到这里拓荒。不过资源丰富的潘多拉星球完全不适合人类生活,这里的空气对人类有毒,本土的动植物是凶猛的掠食者,非常危险。这里的环境也造就了与人类不同的一群生物:10英尺高的蓝色类人生物“Na'vi族”。
由于潘多拉星球环境严酷,地球人传统的宇航服、机甲都不足以保护矿工,于是科学家们转向了克隆技术:他们将地球人的DNA和Na'vi人的DNA结合在一起,制造了一个克隆Na'vi人,这个克隆Na'vi人可以让人类的意识进驻其中,成为地球人在潘多拉星球上自由活动的“化身”。
为了让地球人DNA与Na'vi人DNA更完美的结合,科学家们发现了一个规则,他们从Na'vi人DNA里提取了n种信息,从地球人DNA里提取了m(m<=n)种信息,这两种DNA在结合的时候,就是从这Na'vi的n种信息里选取m种信息,与地球人DNA的m种信息一一结合。由于技术的不完善,在结合信息时不能改变原有DNA信息的顺序,也就是说如果用地球人DNA的第i种信息和Na'vi人DNA的第j种信息结合,那么用地球人DNA的第i+1种信息和Na'vi人DNA的第k种信息结合时就必须满足k>j。为了更完美地结合两种DNA,科学家们计算出了每种信息的结合度,两种信息结合时,他们的结合度之差的绝对值就是它们的不完美度,两种DNA的m种信息结合的不完美度之和就是两种DNA结合的不完美度。如何结合才能使得两种DNA结合的不完美度最小?

输入
第一行,两个数n和m,表示从Na'vi人DNA里提取n种信息,从地球人DNA里提取m种信息;
第二行,n个小于1000的整数,第i个数表示从Na'vi人DNA中提取的第i种信息的结合度;
第三行,m个小于1000的整数,第i个数表示从地球人DNA中提取的第i种信息的结合度

输出
一行,两种DNA结合的最小不完美度。

样例输入:
5 3
1 3 2 3 8
1 2 3

样例输出:
0

数据范围:
30%的数据 0≤m≤n≤20
70%的数据 0≤m≤n≤400
100%的数据 0≤m≤n≤5000

信息

难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者