题目描述
有一种跳棋只需要一个人就可以玩，它是一个1×N的棋盘，棋盘依次用1~N 标号。一开始有一个棋子在1这个位置：
第一步，棋子只可以移动到2这个位置；
接下来每一步，棋子可以选择前进，前进的步数为上一次步数+1；或者后退，后退的步数，必须等于上一次步数。
比如说，第二步走到2这个位置，那么第三步可以选择回到1或者前进到4。
跳棋的目标就是跳到第N格，然后我们将沿途经过的所有格子的值加起来(一个格子经过多次，则代价算多次)，使得这个值的和最小。
现在你有一副大小为N的棋，希望你给出这个最小的和。
输入格式
第一行一个数N，表示棋盘的大小。
接下来N行，每行一个正整数，依次描述每一格的值。
输出格式
一行一个数，表示最小的和。
输入输出样例
输入 #1
6
1
2
3
4
5
6
输出 #1复制
12
说明/提示
对于60%的数据N<=200；
对于100%的数据2<=N<=1000，每个格子的值不超过500。
#include<bits/stdc++.h>
using namespace std;
int n;
int ans;
int f[20005];
int a[20005];
void dfs(int x,int s,int txn)
{
if(s>ans)
return;
if(x==n)
{
ans=min(ans,s);
return;
}
if(x+txn+1<=n)
dfs(x+txn+1,s+a[x+txn+1],txn+1);
if(x-txn>=1)
dfs(x-txn,s+a[x-txn],txn);
}
int main()
{
cin>>n;
ans=1e9;
for(int i=1;i<=n;i++)
cin>>a[i];
dfs(1,0,0);
cout<<ans;
return 0;
}