#P18151. Optimal Train Operation
Optimal Train Operation
Optimal Train Operation
UTPC 铁路有一条笔直的线路,共有 个车站,从起点站到终点站依次编号为 。对每个 ,车站 与 相邻,这两站之间的拥堵度为 。目前,车辆基地设在车站 和 。
在下一次运行图调整中,会重复执行以下操作来修建车辆基地:
- 选择一个车站 (),在那里修建车辆基地,花费 。
之后,会重复执行以下操作来开行列车:
- 选择两个已经建有车辆基地的车站 ,在它们之间开行一列列车。该操作会把区间 内每一段的拥堵度减 1,花费 。
目标是让每一段的拥堵度都降到 0 或以下。求最小总花费。
输入格式
第一行一个整数 ()。
第二行 个整数 ()。
第三行 个整数 ()。
输出格式
输出一个整数,表示最小总花费。
样例 1
输入:
4
3 1 4 1
5 9 2
输出:
15
在车站 3 修建车辆基地,开行 3 列 的列车和 1 列 的列车,总花费为 。
样例 2
输入:
9
28 35 19 27 84 98 78 79 60
40 35 54 63 72 71 27 94
输出:
682