编程题：动态规划

尼古拉违背了自己的意愿，成为了游戏中的主角。游戏在一排N格上进行，编号为1到N。尼古拉最初在1格，可以跳到其他格。尼古拉的第一跳必须是2号方格。每个后续跳转必须满足两个约束：

•如果跳跃是向前的，则必须比前一次跳跃长一平方米。
•如果跳跃方向是向后的，则其长度必须与前一跳跃的长度完全相同。

例如，在第一次跳跃后（在2号方格上时），尼古拉可以跳回1号方格或向前跳到4号方格。
尼古拉每次进入广场都必须支付入场费。尼古拉的目标是尽可能便宜地从1号广场到达N号广场。

编写一个程序，确定尼古拉达到平方N的最小总成本。

### 输入格式:
第一行包含整数$$N，2≤N≤1000$$，表示方格数。
以下$$N$$行中的每一行都包含一个平方（小于500的正整数），表示费用。
费用按1至$$N$$的顺序排列。

### 输出格式:
输出$$Nikola$$达到平方$$N$$的最小总成本。

### 输入样例1:
in
6
1
2
3
4
5
6


### 输出样例1:
out
12


### 输入样例2:
in
8
2
3
4
3
1
6
1
4


### 输出样例2:
out
14


在第一个例子中，在跳到2号方格后，尼古拉跳回到1号方格。从那里他可以跳到3号方格，然后跳到6号方格。





答案：若无答案欢迎评论