问题 25397 --竞赛

25397: 竞赛

时间限制: 1 Sec  内存限制: 128 MB
提交: 27  解决: 15
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][140kb]

题目描述

XX年XX月的某一天,阿狸到黑森林里去玩,不幸被野兽们抓了起来。去觐见动物王国的领袖——巨龙。
动物王国的动物们很不和谐,动不动就会来个决斗,而决斗所破坏掉的森林资源自然全部要国王掏腰包。巨龙知道狐狸是最聪明的【其实是狡猾】,他答应如果阿狸能安排动物们的挑战组合,就答应放了他。
     动物们的决斗很有规律,他们分为两个阵营,决斗开始时两个阵营的动物排成两个队,每个动物有一个破坏值,然后由阿狸来安排比赛,动物们会按照顺序分组进行PK,可以是单挑,群挑,或者是单挑群。具体规则如下:
从后往前,每次从A阵营选出连续k1(k1>0)个动物,他们的破坏值之和为S1,从B阵营选出连续k2(k2>0)个动物,他们的破坏值之和为S2,选出的这些动物将进行决斗,这次破坏导致森林的修整费用为 (S1-K1)*(S2-K2)。决斗直到两个队伍都为空时结束。结束之后,这些决斗的总修整费用就为每次PK修整费用的和。
阿狸的大脑一片空白,只能让你来完成任务救出阿狸。你需要做的就是使这次决斗的费用最小。

输入

第一行两个正整数L1,L2分别表示两阵营的人数;
第二行L1个正整数,描述A阵营每个人的破坏值。
第三行L2个正整数,描述B阵营每个人的破坏值。

输出

一个正整数表示森林的最小修整费用

样例输入

3 2
1 2 3
1 2

样例输出

2

提示

【样例解释】

从后往前数,A中的3和B中的2进行PK,这次的破坏值为:(3-1)*(2-1)=2,然后A中的1,2和B中的1进行PK,这次的破坏值为:(3-1)*(1-1)=0,所以这组数据的结果为2+0=0。

【数据范围】

1<=L1,L2<=2000

来源

[提交][状态]