题目描述
Nikola现在已经成为一个游戏里的重要人物。这个游戏是由一行N个方格,N个方格用1到N的数字表示。Nikola开始是在1号位置,然后能够跳到其他的位置,Nikola的第一跳必须跳到2号位置。随后的每一跳必须满足两个条件:
1、如果是向前跳,必须比前面一跳远一个方格。
2、如果是向后跳,必须和前面一跳一样远。
比如,在第一跳之后(当在2号位置时),Nikola能够跳回1号位置,或者向前跳到4号位置。
每次他跳入一个位置,Nikola必须付费。Nikola的目标是从一号位置尽可能便宜地跳到N号位置。
写一个程序,看看Nikola跳到N号位置时最小的花费。
输入
第一行:包含一个整数N,2≤N≤1000,它是位置的编号。
第2…N+1行:第i+1行表示第I个方格的费用,是一个正整数,绝对不超过500。
输出
输出Nikola跳到N号位置时最小的花费。
Code
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 50,INF = 0x3f3f3f3f;
int n,val[N],f[N][N];
int main()
{std::ios::sync_with_stdio(false);cin >> n;for(int i = 1;i <= n;++i)cin >> val[i];memset(f,0x3f,sizeof(f));f[1][0] = 0;for(int st = 1;st <= n;++st){for(int i = st + 1;i <= n;++i)f[i][st] = min(f[i][st],f[i - st][st - 1] + val[i]);for(int i = n - st;i >= 1;--i)f[i][st] = min(f[i][st],f[i + st][st] + val[i]);}int ans = INF;for(int i = 1;i <= n;++i)ans = min(ans,f[n][i]);cout << ans;return 0;
}