BZPRO
#2448. 挖油
内存限制：128 MiB
时间限制：10 Sec
提交
提交记录
讨论
题目描述
给出一条线段，在左端点点
0
与右端点
n+1
间有
n
个点
(n<=2000)
，并且在
0
到
x
之间的所有点都是有油的，在每个点钻井判断是否有油需要时间
ti
，求能够知道
x
的最坏情况下最少需要多少时间。
输入格式
第一行包含一个数
n
，如题目描述。
第二行包含
n
个数，表示在第
i
个点钻井判断是否有油需要的时间。
输出格式
输出包含一行，最坏情况下最少需要多少时间。
样例
样例输入
4
8 24 12 6
样例输出
42
数据范围与提示
对于100%的数据，n<=2000,ti<=10^6
BZPRO