5846. 挖油
时间限制：1000 MS 内存限制：256 MB
题目描述
### 题目描述 给出一条线段，在左端点\(0\)与右端点\(n + 1\)间有\(n\)个点，并且在\(0\)到\(n\)之间的所有点都是有油的，在每个点钻井判断是否有油需要时间\(t_i\)，求能够知道\(n\)的最坏情况下最少需要多少时间。 ### 输入格式 - 第一行包含一个数\(n\)，如题目描述。 - 第二行包含\(n\)个数，表示在第\(i\)个点钻井判断是否有油需要的时间\(t_i\)。 ### 输出格式 输出包含一行，最坏情况下最少需要多少时间。 ### 样例 #### 样例输入 ``` 4 8 24 12 6 ``` #### 样例输出 ``` 42 ``` ### 数据范围与提示 - \(30\%\)的数据，\(n < 500\)。 - 另有\(20\%\)的数据，\(t_i\)都相等。 - \(80\%\)的数据，\(n < 2000\)。 - 对于\(100\%\)的数据，\(n \leq 6000\)，\(t_i \leq 10^8\)。