luogu#P6507. [CRCI2007-2008] NIKOLA
[CRCI2007-2008] NIKOLA
题目描述
有一行 个格子,编号为 ,Nikola 从 号格子出发,想要前往 号格子。
他的行程包含若干次跳跃,第一次只能跳到 号格子,接下来的跳跃必须满足以下条件:
-
如果他向 号格子的方向跳跃,那么每次必须比前一次多跳一个距离的格子;
-
如果他向 号格子的方向跳跃,那么每次必须与上一次的跳跃距离完全相同。
例如,在第一次跳跃之后(位于 号格),Nikola 可以选择跳到 或者 。
每进入一个格子,Nikola 都要支付相应的入场费。第 个格子需要付费 。他希望在能到达 号格的前提下尽可能少的花钱。你需要求出这个最小值。
输入格式
输入第一行一个整数 ,表示格子的数量。
接下来的 行,每行一个整数 ,依次表示 号格子的入场费。
输出格式
输出一行一个整数,表示最小的花费。
注意:刚开始所在的 号格子不计费,但多次经过同一个格子需要计费。
6
1
2
3
4
5
6
12
8
2
3
4
3
1
6
1
4
14
提示
样例 1 解释
在第一个样例中,Nikola 的路线为 。共花费 。
数据规模与约定
对于 的数据,保证 ,。
说明
题目译自 COCI2007-2008 Regional Competition T2 NIKOLA。