单足跳
Description
游戲在一行N個方塊中進行，編號為1到N，一開始Alice在方塊1中，第一次只能跳到方塊2中，接下來每一次跳躍必須滿足以下兩個限制：
（1） 如果是向前跳（即跳到比現在編號大的方塊），跳躍距離必須比上一次要大1；
（2） 如果是向后跳（即跳到比現在編號小的方塊），跳躍距離必須跟上一次一樣。
例如，第一次跳躍后，Alice可以跳回1也可以跳到4。
每進入一個方塊，Alice必須支付一定的費用，Alice的目標花最少的錢從方塊1跳到方塊N。編程計算最小的花費。
Input
第一行包含一個整數N(2<=N<=1000)，表示方塊的個數。
接下來N行，每行包含一個不超過500的正整數表示進入該方塊的費用。
Output
輸出Alice跳到N的最小花費。
Sample Input
輸入1：
6
1
2
3
4
5
6
輸入2：
8
2
3
4
3
1
6
1
4
Sample Output
輸出1：
12
輸出2：
14
Data Constraint
Hint
【樣例解釋】
樣例1中，在跳到2后，Alice選擇跳回1，再跳到3然后再跳到6。
.
.
.
.
.
.
分析
設f[i,j]表示花費i次跳躍走到j格。
那么轉移就是向前和向后。
往前的情況：
我們會到達j-i這個位置，根據題目意思，花費i步過去
f[i][j-i]=min(f[i][j-i],f[i][j]+v[j-i]);
往后的情況：
我們會往后跳i+1位，即到達j+i+1這個位置，他是花費i+1步過去
if (f[i][j]<2147483647) f[i+1][i+j+1]=f[i][j]+v[i+j+1];
.
.
.
.
.
.
程序：
#include<iostream> using namespace std; long long f[1001][1001],ans=2147483647; int n,v[1500]; int main() {cin>>n;for (int i=1;i<=n;i++)cin>>v[i];for (int i=0;i<=n;i++)for (int j=0;j<=n;j++)f[i][j]=2147483647;f[1][2]=v[2];for (int i=1;i<=n-1;i++){for (int j=n;j>=i+1;j--)f[i][j-i]=min(f[i][j-i],f[i][j]+v[j-i]);for (int j=1;j<=n-1;j++)if (f[i][j]<2147483647) f[i+1][i+j+1]=f[i][j]+v[i+j+1];}for (int i=1;i<=n;i++)ans=min(ans,f[i][n]);cout<<ans;return 0; }轉載于:https://www.cnblogs.com/YYC-0304/p/9499944.html
總結
