长沙noip2009模拟题 第三题 求大神解答

长沙noip2009模拟题 第三题 求大神解答
二．走格子游戏
题目描述：
毕莎设计了一个走格子游戏，游戏是在一行N个格子上进行的，N个格子的编号从1到N。开始时游戏者在第一个格子上，并能从一个格子跳到另一个格子上。跳动是有规定的，第一步只能跳到第2格，后面的跳动必须满足两个条件：
如果往前跳，他必须比前一次跳动增加一个格子；
如果往后跳，他必须与前一次跳动的格子数相同；
比如：第一次跳动后（此时在第2格），他能往后跳到第1格或往前跳到第4格。
每进入一个格子，游戏者都必须支付一定的进入费。游戏者从第1格开始，到达第N格结束，在跳动过程中，尽可能的少去付一些费用。写一个程序计算到达第N格最少支付的费用。
输入数据：
第一行为一个整数N，2<=N<=1000，表示格子数。
后面有N行，每行一个少于500的正整数，表示进入相庆格子的费用。
输出数据：
仅一行，表示支付的最少费用。
输入输出样例：
input
6
1
2
3
4
5
6
output
12
在第一个样例中，跳到第2格后，又跳回到第1格。从第1格再跳到第3格，再从第3格跳到第6格