luogu#P9209. 不灭「不死鸟之尾」
不灭「不死鸟之尾」
题目背景
不死鸟之尾,一种量产型的羽毛。可用作药品。
虽说是量产型,可是从哪里可以得到这种万能之药呢?
题目描述
有一个包含 个停车位的停车场,里面的停车位排成了一排,最左边和最右边都是墙壁。
有 辆车要按顺序依次停入这个停车场,在停入第 辆车时,这辆车要停入的位置左右两边的空位越多,停进去需要的时间也就会越少,具体地,如果其左边连续的空位数量为 ,其右边连续的空位数量为 ,那么停入该辆车所需时间为 ,其中 会给出(特别的,停车所需要的时间不会是负数,所以我们保证 )。
对于连续空位的解释:例如,下图中箭头所指位置左边连续空位为 ,右边连续空位为 。
请依次确定每一辆车停入的位置,使得停入所有车所需时间最小。
输入格式
输入第一行一个整数 。
接下来三行,每行 个整数:第一行第 个数给出 ,第二行第 个数给出 ,第三行第 个数给出 。保证 ,。
输出格式
输出一个数表示所需要的最少时间。
3
18 20 22
1 2 3
1 4 3
54
提示
样例解释 1
第 辆车停入从左往右数第 个停车位,此时该停车位左边有 个连续空位,右边没有连续空位,所需时间 。
第 辆车停入从左往右数第 个停车位,此时该停车位左边没有连续空位,右边有 个连续空位,所需时间 。
第 辆车停入从左往右数第 个停车位,此时该停车位左右都没有连续空位,所需时间 。
停入所有车需要时间 。
数据范围
对于所有数据,保证 ,,。