#2448. 挖油
挖油
题目描述
给出一条线段,在左端点 与右端点 间有 个点,并且在 到 之间的所有点都是有油的,在每个点钻井判断是否有油需要时间 ,求能够知道 的最坏情况下最少需要多少时间。
输入格式
第一行包含一个正整数 ,如题目描述。
第二行包含 个整数,表示在第 个点钻井判断是否有油需要的时间。
输出格式
输出包含一行,最坏情况下最少需要多少时间。
4
8 24 12 6
42
数据规模与约定
对于 的数据,,。
题目来源
2011福建集训
给出一条线段,在左端点 0 与右端点 n+1 间有 n 个点,并且在 0 到 x 之间的所有点都是有油的,在每个点钻井判断是否有油需要时间 ti,求能够知道 x 的最坏情况下最少需要多少时间。
第一行包含一个正整数 n,如题目描述。
第二行包含 n 个整数,表示在第 i 个点钻井判断是否有油需要的时间。
输出包含一行,最坏情况下最少需要多少时间。
4
8 24 12 6
42
对于 100% 的数据,1≤n≤2×103,1≤ti≤106。
2011福建集训